Sum of minimum value of x and y satisfying the equation ax + by = c | Java program for the above approach ; x and y store solution of equation ax + by = g ; Euclidean Algorithm ; store_gcd returns the gcd of a and b ; Function to find any possible solution ; Condition if solution does not exists ; Adjusting the sign of x0 and y0 ; Function to shift solution ; Shifting to obtain another solution ; Function to find minimum value of x and y ; g is the gcd of a and b ; Store sign of a and b ; If x is less than 0 , then shift solution ; If y is less than 0 , then shift solution ; Find intersection such that both x and y are positive ; miny is value of y corresponding to minx ; Returns minimum value of x + y ; Driver Code ; Given a , b , and c ; Function call
import java . lang . * ; class GFG { public static int x = 0 , y = 0 , x1 = 0 , y1 = 0 ; public static int x0 = 0 , y0 = 0 , g = 0 ; public static int gcd ( int a , int b ) { if ( b == 0 ) { x = 1 ; y = 0 ; return a ; } int store_gcd = gcd ( b , a % b ) ; x = y1 ; y = x1 - y1 * ( a / b ) ; return store_gcd ; } public static int possible_solution ( int a , int b , int c ) { g = gcd ( Math . abs ( a ) , Math . abs ( b ) ) ; if ( c % g != 0 ) { return 0 ; } x0 *= c / g ; y0 *= c / g ; if ( a < 0 ) x0 *= - 1 ; if ( b < 0 ) y0 *= - 1 ; return 1 ; } public static void shift_solution ( int a , int b , int shift_var ) { x += shift_var * b ; y -= shift_var * a ; } public static int find_min_sum ( int a , int b , int c ) { int x = 0 , y = 0 , g = 0 ; if ( possible_solution ( a , b , c ) == 0 ) return - 1 ; if ( g != 0 ) { a /= g ; b /= g ; } int sign_a = a > 0 ? + 1 : - 1 ; int sign_b = b > 0 ? + 1 : - 1 ; shift_solution ( a , b , - x / b ) ; if ( x < 0 ) shift_solution ( a , b , sign_b ) ; int minx1 = x ; shift_solution ( a , b , y / a ) ; if ( y < 0 ) shift_solution ( a , b , - sign_a ) ; int minx2 = x ; if ( minx2 > x ) { int temp = minx2 ; minx2 = x ; x = temp ; } int minx = Math . max ( minx1 , minx2 ) ; if ( minx > x ) return - 1 ; int miny = ( c - a * x ) / b ; return ( miny + minx ) ; } public static void main ( String [ ] args ) { int a = 2 , b = 2 , c = 0 ; System . out . println ( find_min_sum ( a , b , c ) ) ; } }