Input: N = 8, M = 4
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
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)))