Reach the numbers by making jumps of two given lengths

https://www.geeksforgeeks.org/reach-the-numbers-by-making-jumps-of-two-given-lengths/

Given integers k, d1, d2 and an integer array arr[]. Starting from number k you are allowed to make jumps of size d1and d2 i.e. all the possible moves from k are:

• k + d1 and k – d1
• k + d2 and k – d2

The task is to find which of the numbers from the array are reachable from k making any number of jumps and any given jump is either of size d1 or d2. For every number print 1 if its reachable else print 0.

Approach: Any number x that is reachable from k with jumps d1 or d2 will be of the form x = k + (i * d1) + (j * d2)where i and j are integers.
Let the GCD of d1 and d2 be gcd. Since, gcd divides both d1 and d2. Therefore we can write d1 = m1 * gcd and d2 = m2 * gcd where m1 and m2 are integers
And x = k + gcd * (i * m1 + j * m2) = k + M * gcd.
So, any number x that is reachable from k should satisfy (x – k) % gcd = 0.

// Recursive function to return gcd of a and b 

    static int __gcd(int a, int b) 

    { 

        // Everything divides 0  

        if (a == 0) 

          return b; 

        if (b == 0) 

          return a; 

         

        // base case 

        if (a == b) 

            return a; 

         

        // a is greater 

        if (a > b) 

            return __gcd(a-b, b); 

        return __gcd(a, b-a); 

    } 

  

  

      

  

// Function that returns the vector containing the

// result for the reachability of the required numbers

static void reachTheNums(int nums[], int k, int d1, int d2, int n)

{

    int i;

    int ans[] = new int[n];

    int gcd = __gcd(d1, d2);

  

    for (i = 0; i < n; i++) {

        int x = nums[i] - k;

  

        // If distance x is coverable

        if (x % gcd == 0)

            ans[i] = 1;

        else

            ans[i] = 0;

    }

  

    for (i = 0; i < n; i++)

        System.out.print(ans[i] + " ");

}