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.

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;
}

You can also try this code with Online C++ Compiler
Run Code
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 Graph, Binary Tree, BFS vs DFS, Check 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 Algorithms, Competitive Programming, JavaScript, System Design, and many more!
Do upvote our blogs if you find them helpful and engaging!
Happy Learning!