Sum of minimum value of x and y satisfying the equation ax + by = c | Python3 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 ; Given a , b , and c ; Function call
x , y , x1 , y1 = 0 , 0 , 0 , 0 NEW_LINE x0 , y0 , g = 0 , 0 , 0 NEW_LINE def gcd ( a , b ) : NEW_LINE INDENT global x , y , x1 , y1 NEW_LINE if ( b == 0 ) : NEW_LINE INDENT x = 1 NEW_LINE y = 0 NEW_LINE return a NEW_LINE DEDENT store_gcd = gcd ( b , a % b ) NEW_LINE x = y1 NEW_LINE y = x1 - y1 * ( a // b ) NEW_LINE return store_gcd NEW_LINE DEDENT def possible_solution ( a , b , c ) : NEW_LINE INDENT global x0 , y0 , g NEW_LINE g = gcd ( abs ( a ) , abs ( b ) ) NEW_LINE if ( c % g != 0 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT x0 *= c // g NEW_LINE y0 *= c // g NEW_LINE if ( a < 0 ) : NEW_LINE INDENT x0 *= - 1 NEW_LINE DEDENT if ( b < 0 ) : NEW_LINE INDENT y0 *= - 1 NEW_LINE DEDENT return 1 NEW_LINE DEDENT def shift_solution ( a , b , shift_var ) : NEW_LINE INDENT global x , y NEW_LINE x += shift_var * b NEW_LINE y -= shift_var * a NEW_LINE DEDENT def find_min_sum ( a , b , c ) : NEW_LINE INDENT global x , y , g NEW_LINE x , y , g = 0 , 0 , 0 NEW_LINE if ( possible_solution ( a , b , c ) == 0 ) : NEW_LINE INDENT return - 1 NEW_LINE DEDENT if ( g != 0 ) : NEW_LINE INDENT a //= g NEW_LINE b //= g NEW_LINE DEDENT if a > 0 : NEW_LINE INDENT sign_a = 1 NEW_LINE DEDENT else : NEW_LINE INDENT sign_a = - 1 NEW_LINE DEDENT if b > 0 : NEW_LINE INDENT sign_b = 1 NEW_LINE DEDENT else : NEW_LINE INDENT sign_b = - 1 NEW_LINE DEDENT shift_solution ( a , b , - x // b ) NEW_LINE if ( x < 0 ) : NEW_LINE INDENT shift_solution ( a , b , sign_b ) NEW_LINE DEDENT minx1 = x NEW_LINE shift_solution ( a , b , y // a ) NEW_LINE if ( y < 0 ) : NEW_LINE INDENT shift_solution ( a , b , - sign_a ) NEW_LINE DEDENT minx2 = x NEW_LINE if ( minx2 > x ) : NEW_LINE INDENT temp = minx2 NEW_LINE minx2 = x NEW_LINE x = temp NEW_LINE DEDENT minx = max ( minx1 , minx2 ) NEW_LINE if ( minx > x ) : NEW_LINE INDENT return - 1 NEW_LINE DEDENT miny = ( c - a * x ) // b NEW_LINE return ( miny + minx ) NEW_LINE DEDENT a , b , c = 2 , 2 , 0 NEW_LINE print ( find_min_sum ( a , b , c ) ) NEW_LINE