Select Page

# Number of distinct GCD by adding same number with given two integers

Kashish Kumar
Published: July 13, 2022

Given two positive integers N and M, the task is to find the number of different GCDs which can be formed by adding an integer K to both N and M, where K ≥ 0.

Examples:

Input: N = 8, M = 4
Output: 3
Explanation: If K = 0, then GCD(8, 4) = 4,
If K = 1, then GCD(9, 5) = 1,
If K = 2, then GCD(10, 6) = 2

Input: N = 7, M = 10
Output: 2
Explanation: If K = 0, then GCD(7, 10) = 1,
If K = 2, then GCD(9, 12) = 3

Approach: The problem can be solved based on the following mathematical idea:

The maximum value of GCD formed after adding any value of K will be abs(N – M).
Other than the above result if any other GCD is formed, that will be a perfect divisor of abs(N – M).

Follow the steps below to implement the above idea:

• Find the absolute difference between N and M (say X).
• Find the number of unique divisors of the X.
• Return this value as the required answer.

Below is the implementation of the above approach:

## Java

 ` ` `import` `java.util.*;`` ` `class` `GFG {`` ` `    ``    ``public` `static` `void` `main(String[] args)``    ``{``        ``int` `N = ``8``;``        ``int` `M = ``4``;`` ` `        ``        ``System.out.println(distinctGCDs(N, M));``    ``}`` ` `    ``    ``    ``public` `static` `int` `distinctGCDs(``int` `N, ``int` `M)``    ``{``        ``        ``        ``Set hs = ``new` `HashSet<>();``        ``int` `diff = Math.abs(N - M);`` ` `        ``        ``        ``for` `(``int` `i = ``1``; i * i <= diff; i++) {`` ` `            ``            ``            ``if` `(diff % i == ``0``) {``                ``hs.add(i);``                ``hs.add(diff / i);``            ``}``        ``}`` ` `        ``        ``        ``return` `hs.size();``    ``}``}`

Time Complexity: O(sqrt(abs(N – M)))
Auxiliary Space: O(sqrt(abs(N – M)))

Source: www.geeksforgeeks.org