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

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:

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