Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Linear Diophantine Equation
3.
Examples
4.
Working
5.
Implementation in C++
6.
Complexity Analysis
7.
Frequently Asked Questions
7.1.
What is Diophantine Equation?
7.2.
What is the meaning of Diophantine?
7.3.
Who is the father of polynomials?
7.4.
Who was the first to solve the Diophantine equation?
8.
Conclusion
Last Updated: Mar 27, 2024
Easy

Linear Diophantine Equation

Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

Introduction

This article will discuss the Linear Diophantine Equation. Many of you may not have heard about the Linear Diophantine Equation. 

In Linear Diophantine Equation, most of you are aware of linear, but the question comes what do you mean by Diophantine Equation?

A Diophantine equation is a polynomial equation whose solutions are restricted to integral values. It may contain two or more unknown parameters. It is named after the ancient Greek mathematician Diophantus.

Now, coming to the Linear Diophantine Equation. 

Linear Diophantine Equation Image

Linear Diophantine Equations is a first-degree equation of the Diophantine Equations. The general form of this is:

ax+by=c

Here a,b, and c are given integers, and x and y are unknown integers.

Also see, Longest Common Substring and Rabin Karp Algorithm

Linear Diophantine Equation

The general form of the Linear Diophantine Equation can be written as ax+by=c.

Therefore, the integral solution exists if and only if the GCD of and divides perfectly.

If GCD(a,b) divides c, then only the integral solution exists.

However, A degenerate case arises when a=b=0. We either have no or infinitely many solutions, depending on whether c=0 or not. Therefore, we will ignore this case.

Now. let's see an example for better understanding.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Examples

Input: a = 1, b = 2, c = 3

Output: Possible

Explanation: The Equation turns out to be 1x + 2y = 3. One integral solution would be x = 1 , y = 1

 

Input: a = 12, b = 21, c = 80

Output: Not Possible

Explanation:  There is no common factor for the entire equation. Since the LHS have a common factor of 3, 3(4a+7b)=80. This means that (4a+7b) is also an integer. But (4a+7b)=80/3, which is not an integer. Therefore 0 integral values of x and y exists that can satisfy the equation 12a+21b=80.

 

Input: a = 12, b = 8, c = 68

Output: Possible

Explanation: Various integral solutions possible are,(5,1), (3,4), (1,7).

 

Let's discuss the internal working of the Linear Diophantine Equation.

Read More About, Data Structures and Algorithms and Application of Graph in Data Structure

Working

The general equation of the Linear Diophantine Equation is ax+by=c.

Now. let’s suppose the GCD(a,b)=g.

Since g divides a and b, therefore it also divides ax+by.

And from the above equation ax+by=c.

Thus g also divides c.

Working Image

Now, let's see the implementation.

Implementation in C++

#include <bits/stdc++.h>
using namespace std;
 
//function to find the GCD of two numbers
int findGCD(int a, int b)
{
    while(a!=b){
        if(a>b)
            a=a-b;
        else
            b=b-a;
        return a;
    }
}
 
//function checks if integral solutions are
// possible
bool isPossible(int a, int b, int c)
{
    return (c%findGCD(a,b) == 0);
}
 
//driver function
int main()
{
    // Example 1
    int a = 1, b = 2, c = 3;
    if (isPossible(a, b, c))
        cout << "Possible\n";
    else                    
        cout << "Not Possible\n";
 
    // Example 2
    a = 12, b = 21, c = 80;
    if (isPossible(a, b, c))
        cout << "Possible\n";
    else                    
        cout << "Not Possible\n";
 
    // Example 3
    a = 12, b = 8, c = 68;
    if (isPossible(a, b, c))
        cout << "Possible\n";
    else                    
        cout << "Not Possible\n";
 
    return 0;
}

 

Output:

Possible
Not Possible
Possible

 

Also see, Morris Traversal for Inorder.

Complexity Analysis

Time Complexity: The time complexity is O(min(a,b)). This is because to check the Greatest Common Divisor of two integers, it depends on the minimum of two numbers using the concept of Euclidean Algorithm.

Space Complexity: The space complexity is O(1).

We have discussed the Examples, Internal working, and the Linear Diophantine Equation implementation.

Let's discuss some FAQs related to the Linear Diophantine Equation.

Frequently Asked Questions

What is Diophantine Equation?

The diophantine Equation is a polynomial equation in which only integral solutions are allowed.

What is the meaning of Diophantine?

It is an indeterminate polynomial equation that has integral coefficients and for which it is required to find all integral solutions.

Who is the father of polynomials?

Diophantus of Alexandria is known as the father of Polynomials.

Who was the first to solve the Diophantine equation?

Diophantine Equation is named in honor of the 3rd-century Greek mathematician Diophantus of Alexandria, but these equations were first systematically solved by Aryabhata (An Indian Mathematician). 

Conclusion

We have discussed the Linear Diophantine Equation with examples, internal working, and implementation, followed by some FAQs.

After reading about the Linear Diophantine Equation, are you not feeling excited to read/explore more articles on Data Structures and Algorithms? Don't worry; Coding Ninjas has you covered. See GraphBinary TreeBFS vs DFSCheck for Balanced Parentheses in an Expression, and Stack to learn.

Want to know how to improve your logics in programming? Check out 7 Tips to improve logic for programming

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem Design, and many more! 

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

Previous article
How to Convert byte Array to String in Java
Next article
Gray to Binary
Live masterclass