Given three integers a, b, and c representing a linear equation of the form: ax + by = c. The task is to find the initial integral solution of the given equation if a finite solution exists.
A Linear Diophantine equation (LDE) is an equation with 2 or more integer unknowns and the integer unknowns are each to at most degree of 1. Linear Diophantine equation in two variables takes the form of ax+by=c, where x,y are integer variables and a, b, c are integer constants. x and y are unknown variables.
Examples:
Input: a = 4, b = 18, c = 10
Output: x = -20, y = 5
Explanation: (-20)*4 + (5)*18 = 10
Input: a = 9, b = 12, c = 5
Output: No Solutions exists
Approach:
- First, check if a and b are non-zero.
- If both of them are zero and c is non-zero then, no solution exists. If c is also zero then infinite solution exits.
- For given a and b, calculate the value of x1, y1, and gcd using Extended Euclidean Algorithm.
- Now, for a solution to existing gcd(a, b) should be multiple of c.
- Calculate the solution of the equation as follows:
x = x1 * ( c / gcd ) y = y1 * ( c / gcd )
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h> using namespace std;// Function to implement the extended// euclid algorithmint gcd_extend(int a, int b, int& x, int& y){ // Base Case if (b == 0) { x = 1; y = 0; return a; } // Recursively find the gcd else { int g = gcd_extend(b, a % b, x, y); int x1 = x, y1 = y; x = y1; y = x1 - (a / b) * y1; return g; }}// Function to print the solutions of// the given equations ax + by = cvoid print_solution(int a, int b, int c){ int x, y; if (a == 0 && b == 0) { // Condition for infinite solutions if (c == 0) { cout << "Infinite Solutions Exist" << endl; } // Condition for no solutions exist else { cout << "No Solution exists" << endl; } } int gcd = gcd_extend(a, b, x, y); // Condition for no solutions exist if (c % gcd != 0) { cout << "No Solution exists" << endl; } else { // Print the solution cout << "x = " << x * (c / gcd) << ", y = " << y * (c / gcd) << endl; }}// Driver Codeint main(void){ int a, b, c; // Given coefficients a = 4; b = 18; c = 10; // Function Call print_solution(a, b, c); return 0;} |
Java
// Java program for the above approachclass GFG{static int x, y; // Function to implement the extended// euclid algorithmstatic int gcd_extend(int a, int b){ // Base Case if (b == 0) { x = 1; y = 0; return a; } // Recursively find the gcd else { int g = gcd_extend(b, a % b); int x1 = x, y1 = y; x = y1; y = x1 - (a / b) * y1; return g; }}// Function to print the solutions of// the given equations ax + by = cstatic void print_solution(int a, int b, int c){ if (a == 0 && b == 0) { // Condition for infinite solutions if (c == 0) { System.out.print("Infinite Solutions " + "Exist" + "\n"); } // Condition for no solutions exist else { System.out.print("No Solution exists" + "\n"); } } int gcd = gcd_extend(a, b); // Condition for no solutions exist if (c % gcd != 0) { System.out.print("No Solution exists" + "\n"); } else { // Print the solution System.out.print("x = " + x * (c / gcd) + ", y = " + y * (c / gcd) + "\n"); }}// Driver Codepublic static void main(String[] args) { int a, b, c; // Given coefficients a = 4; b = 18; c = 10; // Function Call print_solution(a, b, c);}}// This code is contributed by Rajput-Ji |
Python3
# Python3 program for the above approach import mathx, y = 0, 0 # Function to implement the extended# euclid algorithmdef gcd_extend(a, b): global x, y # Base Case if (b == 0): x = 1 y = 0 return a # Recursively find the gcd else: g = gcd_extend(b, a % b) x1, y1 = x, y x = y1 y = x1 - math.floor(a / b) * y1 return g # Function to print the solutions of# the given equations ax + by = cdef print_solution(a, b, c): if (a == 0 and b == 0): # Condition for infinite solutions if (c == 0): print("Infinite Solutions Exist") # Condition for no solutions exist else : print("No Solution exists") gcd = gcd_extend(a, b) # Condition for no solutions exist if (c % gcd != 0): print("No Solution exists") else: # Print the solution print("x = ", int(x * (c / gcd)), ", y = ", int(y * (c / gcd)), sep = "") # Given coefficientsa = 4b = 18c = 10# Function Callprint_solution(a, b, c)# This code is contributed by decode2207. |
C#
// C# program for the above approachusing System;class GFG{static int x, y; // Function to implement the extended// euclid algorithmstatic int gcd_extend(int a, int b){ // Base Case if (b == 0) { x = 1; y = 0; return a; } // Recursively find the gcd else { int g = gcd_extend(b, a % b); int x1 = x, y1 = y; x = y1; y = x1 - (a / b) * y1; return g; }}// Function to print the solutions of// the given equations ax + by = cstatic void print_solution(int a, int b, int c){ if (a == 0 && b == 0) { // Condition for infinite solutions if (c == 0) { Console.Write("Infinite Solutions " + "Exist" + "\n"); } // Condition for no solutions exist else { Console.Write("No Solution exists" + "\n"); } } int gcd = gcd_extend(a, b); // Condition for no solutions exist if (c % gcd != 0) { Console.Write("No Solution exists" + "\n"); } else { // Print the solution Console.Write("x = " + x * (c / gcd) + ", y = " + y * (c / gcd) + "\n"); }}// Driver Codepublic static void Main(String[] args) { int a, b, c; // Given coefficients a = 4; b = 18; c = 10; // Function call print_solution(a, b, c);}}// This code contributed by amal kumar choubey |
Javascript
<script>// Javascript program for the above approach let x, y; // Function to implement the extended// euclid algorithmfunction gcd_extend(a, b){ // Base Case if (b == 0) { x = 1; y = 0; return a; } // Recursively find the gcd else { let g = gcd_extend(b, a % b); let x1 = x, y1 = y; x = y1; y = x1 - Math.floor(a / b) * y1; return g; }}// Function to print the solutions of// the given equations ax + by = cfunction print_solution(a, b, c){ if (a == 0 && b == 0) { // Condition for infinite solutions if (c == 0) { document.write("Infinite Solutions " + "Exist" + "\n"); } // Condition for no solutions exist else { document.write("No Solution exists" + "\n"); } } let gcd = gcd_extend(a, b); // Condition for no solutions exist if (c % gcd != 0) { document.write("No Solution exists" + "\n"); } else { // Print the solution document.write("x = " + x * (c / gcd) + ", y = " + y * (c / gcd) + "<br/>"); }}// Driver Code let a, b, c; // Given coefficients a = 4; b = 18; c = 10; // Function Call print_solution(a, b, c); </script> |
Output:
x = -20, y = 5
Time Complexity: O(log(max(A, B))), where A and B are the coefficient of x and y in the given linear equation.
Auxiliary Space: O(1)
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!