Select Page

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

Kashish Kumar
Published: July 13, 2022

View Discussion

Improve Article

Save Article

Like Article

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<Integer> 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