There are two children harry and garry. Harry is having some coins of value a and garry is having some coins of value b (a and b are positive numbers). They want to get the greatest common divisor d of a and b by adding or subtracting multiples of these two coins. let us say that a = 25 and b=45 then their gcd is 5 and 5 = 2×25 - 45 i.e. gcd can…

CandidateCode.java

import java.io.*;
public class CandidateCode 
{
    public static int gcd_value;

    public static int gcd(int a, int b) {
        if (b == 0) {
            return Math.abs(a);
        }
        return gcd(b, a % b);
    }

    public static int[] coins_value(int[] input1)
    {
        gcd_value = gcd( input1[0], input1[1] );

        int j = 1, i = 1, found = 0;
        int[] rArray = new int[2];

        while ( found == 0 )
        {
            int na = input1[0] * i;
            int nb = input1[1] * j;
            int tt = na - nb;

            int x = Math.abs(tt);
            if ( x == gcd_value ) {
                if ( tt < 0 ) {
                    rArray[0] = -i;
                    rArray[1] = j;
                }
                else {
                    rArray[0] = i;
                    rArray[1] = -j;
                }
                found = 1;
            }

            if ( tt > gcd_value ) {
                j = j + 1;
            }

            i++;
        }
        return rArray;
    }
}