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 mathÂ
x, 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!
