Time ComGiven three integers a, b, and c representing a linear equation of the form ax + by = c, the task is to find the solution (x, y) of the given equation such that (x + y) is minimized. If no solution exists for the above equation then print “-1”.
Note: x and y are non negative integers.
Examples:
Input: a = 2, b = 2, c = 0
Output: 0
Explanation:
The given equation is 2x + 2y = 0.
Therefore, x = 0 and y = 0 is the required solution with minimum value of (x + y).Input: a = 2, b = 2, c = 1
Output: -1
Explanation:
The given equation is 2x + 2y = 1.
No solution exists for the given equation for positive values of x and y.
Approach: To solve the above problem, find any solution say (x, y) of the given Linear Diophantine Equation and then accordingly find value of x and to minimised the sum.
Below is the solution (x’, y’) of the given equation:
[Tex]y’ = y – k * \frac{a}{g} [/Tex]
where g is gcd(a, b) and k is any integer.
[Tex]x’ + y’ = x + y + k*\frac{b-a}{g} [/Tex]
[Tex]y’ = y – k * \frac{a}{g} [/Tex]
[Tex]x’ + y’ = x + y + k*\frac{b-a}{g} [/Tex]From the above equation we observe that:
- If a is less than b, we need to select the smallest possible value of K.
- Else, if a is greater than b, we need to select the largest possible value of K.
- If a = b, all solutions will have the same sum (x + y).
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the gcd of a & b // by Euclid's method // x and y store solution of // equation ax + by = g 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); // Euclidean Algorithm *x = y1; *y = x1 - y1 * (a / b); // store_gcd returns // the gcd of a and b return store_gcd; } // Function to find any // possible solution int possible_solution(int a, int b, int c, int* x0, int* y0, int* g) { *g = gcd(fabs(a), fabs(b), x0, y0); // Condition if solution // does not exists if (c % *g) { return 0; } *x0 *= c / *g; *y0 *= c / *g; // Adjusting the sign // of x0 and y0 if (a < 0) *x0 *= -1; if (b < 0) *y0 *= -1; return 1; } // Function to shift solution void shift_solution(int* x, int* y, int a, int b, int shift_var) { // Shifting to obtain // another solution *x += shift_var * b; *y -= shift_var * a; } // Function to find minimum // value of x and y int find_min_sum(int a, int b, int c) { int x, y, g; // g is the gcd of a and b if (!possible_solution(a, b, c, &x, &y, &g)) return -1; a /= g; b /= g; // Store sign of a and b int sign_a = a > 0 ? +1 : -1; int sign_b = b > 0 ? +1 : -1; shift_solution(&x, &y, a, b, -x / b); // If x is less than 0, then // shift solution if (x < 0) shift_solution(&x, &y, a, b, sign_b); int minx1 = x; shift_solution(&x, &y, a, b, y / a); // If y is less than 0, then // shift solution 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); // Find intersection such // that both x and y are positive if (minx > x) return -1; // miny is value of y // corresponding to minx int miny = (c - a * x) / b; // Returns minimum value of x+y return (miny + minx); } // Driver Code int main() { // Given a, b, and c int a = 2, b = 2, c = 0; // Function Call cout << find_min_sum(a, b, c) << "\n"; return 0; } |
Java
// Java program for the above approach 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;// Function to find the gcd of a & b // by Euclid's method // x and y store solution of // equation ax + by = g public static int gcd(int a, int b){ if (b == 0) { x = 1; y = 0; return a; } int store_gcd = gcd(b, a % b); // Euclidean Algorithm x = y1; y = x1 - y1 * (a / b); // store_gcd returns // the gcd of a and b return store_gcd;}// Function to find any // possible solution public static int possible_solution(int a, int b, int c){ g = gcd(Math.abs(a), Math.abs(b)); // Condition if solution // does not exists if (c % g != 0) { return 0; } x0 *= c / g; y0 *= c / g; // Adjusting the sign // of x0 and y0 if (a < 0) x0 *= -1; if (b < 0) y0 *= -1; return 1;}// Function to shift solutionpublic static void shift_solution(int a, int b, int shift_var){ // Shifting to obtain // another solution x += shift_var * b; y -= shift_var * a;}// Function to find minimum// value of x and ypublic static int find_min_sum(int a, int b, int c){ int x = 0, y = 0, g = 0; // g is the gcd of a and b if (possible_solution(a, b, c) == 0) return -1; if (g != 0) { a /= g; b /= g; } // Store sign of a and b int sign_a = a > 0 ? + 1 : -1; int sign_b = b > 0 ? + 1 : -1; shift_solution(a, b, -x / b); // If x is less than 0, then // shift solution if (x < 0) shift_solution(a, b, sign_b); int minx1 = x; shift_solution(a, b, y / a); // If y is less than 0, then // shift solution 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); // Find intersection such // that both x and y are positive if (minx > x) return -1; // miny is value of y // corresponding to minx int miny = (c - a * x) / b; // Returns minimum value of x+y return (miny + minx);}// Driver Codepublic static void main(String[] args){ // Given a, b, and c int a = 2, b = 2, c = 0; // Function call System.out.println(find_min_sum(a, b, c));}}// This code is contributed by grand_master |
Python3
# Python3 program for the # above approachx, y, x1, y1 = 0, 0, 0, 0x0, y0, g = 0, 0, 0# Function to find the gcd # of a & b by Euclid's method# x and y store solution of# equation ax + by = gdef gcd(a, b) : global x, y, x1, y1 if (b == 0) : x = 1 y = 0 return a store_gcd = gcd(b, a % b) # Euclidean Algorithm x = y1 y = x1 - y1 * (a // b) # store_gcd returns # the gcd of a and b return store_gcd# Function to find any# possible solutiondef possible_solution(a, b, c) : global x0, y0, g g = gcd(abs(a), abs(b)) # Condition if solution # does not exists if (c % g != 0) : return 0 x0 *= c // g y0 *= c // g # Adjusting the sign # of x0 and y0 if (a < 0) : x0 *= -1 if (b < 0) : y0 *= -1 return 1# Function to shift solutiondef shift_solution(a, b, shift_var) : global x, y # Shifting to obtain # another solution x += shift_var * b y -= shift_var * a# Function to find minimum# value of x and ydef find_min_sum(a, b, c) : global x, y, g x, y, g = 0, 0, 0 # g is the gcd of a and b if (possible_solution(a, b, c) == 0) : return -1 if (g != 0) : a //= g b //= g # Store sign of a and b if a > 0 : sign_a = 1 else : sign_a = -1 if b > 0 : sign_b = 1 else : sign_b = -1 shift_solution(a, b, -x // b) # If x is less than 0, # then shift solution if (x < 0) : shift_solution(a, b, sign_b) minx1 = x shift_solution(a, b, y // a) # If y is less than 0, # then shift solution if (y < 0) : shift_solution(a, b, -sign_a) minx2 = x if (minx2 > x) : temp = minx2 minx2 = x x = temp minx = max(minx1, minx2) # Find intersection such # that both x and y are positive if (minx > x) : return -1 # miny is value of y # corresponding to minx miny = (c - a * x) // b # Returns minimum value # of x + y return (miny + minx)# Given a, b, and ca, b, c = 2, 2, 0# Function callprint(find_min_sum(a, b, c))# This code is contributed by divyesh072019 |
C#
// C# program for the // above approachusing System;class GFG{public static int x = 0, y = 0, x1 = 0, y1 = 0;public static int x0 = 0, y0 = 0, g = 0;// Function to find the gcd // of a & b by Euclid's method// x and y store solution of// equation ax + by = gpublic static int gcd(int a, int b){ if (b == 0) { x = 1; y = 0; return a; } int store_gcd = gcd(b, a % b); // Euclidean Algorithm x = y1; y = x1 - y1 * (a / b); // store_gcd returns // the gcd of a and b return store_gcd;}// Function to find any// possible solutionpublic static int possible_solution(int a, int b, int c){ g = gcd(Math.Abs(a), Math.Abs(b)); // Condition if solution // does not exists if (c % g != 0) { return 0; } x0 *= c / g; y0 *= c / g; // Adjusting the sign // of x0 and y0 if (a < 0) x0 *= -1; if (b < 0) y0 *= -1; return 1;}// Function to shift solutionpublic static void shift_solution(int a, int b, int shift_var){ // Shifting to obtain // another solution x += shift_var * b; y -= shift_var * a;}// Function to find minimum// value of x and ypublic static int find_min_sum(int a, int b, int c){ int x = 0, y = 0, g = 0; // g is the gcd of a and b if (possible_solution(a, b, c) == 0) return -1; if (g != 0) { a /= g; b /= g; } // Store sign of a and b int sign_a = a > 0 ? +1 : -1; int sign_b = b > 0 ? +1 : -1; shift_solution(a, b, -x / b); // If x is less than 0, // then shift solution if (x < 0) shift_solution(a, b, sign_b); int minx1 = x; shift_solution(a, b, y / a); // If y is less than 0, // then shift solution 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); // Find intersection such // that both x and y are positive if (minx > x) return -1; // miny is value of y // corresponding to minx int miny = (c - a * x) / b; // Returns minimum value // of x + y return (miny + minx);}// Driver Codepublic static void Main(String[] args){ // Given a, b, and c int a = 2, b = 2, c = 0; // Function call Console.Write(find_min_sum(a, b, c));}}// This code is contributed by Chitranayal |
Javascript
<script> // Javascript program for the above approach let x = 0, y = 0, x1 = 0, y1 = 0; let x0 = 0, y0 = 0, g = 0; // Function to find the gcd // of a & b by Euclid's method // x and y store solution of // equation ax + by = g function gcd(a, b) { if (b == 0) { x = 1; y = 0; return a; } let store_gcd = gcd(b, a % b); // Euclidean Algorithm x = y1; y = x1 - y1 * parseInt(a / b, 10); // store_gcd returns // the gcd of a and b return store_gcd; } // Function to find any // possible solution function possible_solution(a, b, c) { g = gcd(Math.abs(a), Math.abs(b)); // Condition if solution // does not exists if (c % g != 0) { return 0; } x0 *= parseInt(c / g, 10); y0 *= parseInt(c / g, 10); // Adjusting the sign // of x0 and y0 if (a < 0) x0 *= -1; if (b < 0) y0 *= -1; return 1; } // Function to shift solution function shift_solution(a, b, shift_var) { // Shifting to obtain // another solution x += shift_var * b; y -= shift_var * a; } // Function to find minimum // value of x and y function find_min_sum(a, b, c) { let x = 0, y = 0, g = 0; // g is the gcd of a and b if (possible_solution(a, b, c) == 0) return -1; if (g != 0) { a = parseInt(a / g, 10); b = parseInt(b / g, 10); } // Store sign of a and b let sign_a = a > 0 ? +1 : -1; let sign_b = b > 0 ? +1 : -1; shift_solution(a, b, parseInt(-x / b, 10)); // If x is less than 0, // then shift solution if (x < 0) shift_solution(a, b, sign_b); let minx1 = x; shift_solution(a, b, parseInt(y / a, 10)); // If y is less than 0, // then shift solution if (y < 0) shift_solution(a, b, -sign_a); let minx2 = x; if (minx2 > x) { let temp = minx2; minx2 = x; x = temp; } let minx = Math.max(minx1, minx2); // Find intersection such // that both x and y are positive if (minx > x) return -1; // miny is value of y // corresponding to minx let miny = parseInt((c - a * x) / b, 10); // Returns minimum value // of x + y return (miny + minx); } // Given a, b, and c let a = 2, b = 2, c = 0; // Function call document.write(find_min_sum(a, b, c)); </script> |
Output:
0
Time Complexity: O(loga+logb) = O(logn) , time used to find gcd
Auxiliary Space: O(1) , as no extra space is used
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
