Sum of minimum value of x and y satisfying the equation ax + by = c | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int gcd ( int a , int b , int * x , int * y ) { if ( b == 0 ) { * x = 1 ; * y = 0 ; return a ; } int x1 , y1 ; int store_gcd = gcd ( b , a % b , & x1 , & y1 ) ; * x = y1 ; * y = x1 - y1 * ( a / b ) ; return store_gcd ; } int possible_solution ( int a , int b , int c , int * x0 , int * y0 , int * g ) { * g = gcd ( fabs ( a ) , fabs ( b ) , x0 , y0 ) ; if ( c % * g ) { return 0 ; } * x0 *= c / * g ; * y0 *= c / * g ; if ( a < 0 ) * x0 *= -1 ; if ( b < 0 ) * y0 *= -1 ; return 1 ; } void shift_solution ( int * x , int * y , int a , int b , int shift_var ) { * x += shift_var * b ; * y -= shift_var * a ; } int find_min_sum ( int a , int b , int c ) { int x , y , g ; if ( ! possible_solution ( a , b , c , & x , & y , & g ) ) return -1 ; a /= g ; b /= g ; int sign_a = a > 0 ? +1 : -1 ; int sign_b = b > 0 ? +1 : -1 ; shift_solution ( & x , & y , a , b , - x / b ) ; if ( x < 0 ) shift_solution ( & x , & y , a , b , sign_b ) ; int minx1 = x ; shift_solution ( & x , & y , a , b , y / a ) ; if ( y < 0 ) shift_solution ( & x , & y , a , b , - sign_a ) ; int minx2 = x ; if ( minx2 > x ) swap ( minx2 , x ) ; int minx = max ( minx1 , minx2 ) ; if ( minx > x ) return -1 ; int miny = ( c - a * x ) / b ; return ( miny + minx ) ; } int main ( ) { int a = 2 , b = 2 , c = 0 ; cout << find_min_sum ( a , b , c ) << " STRNEWLINE " ; return 0 ; }