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

**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!