Last Updated: 17 Jun, 2021

Linear Equation

Moderate

Asked in companies

Solve now

Problem statement

Ninja has been given an assignment by his teacher. He has been given three integers ‘a’,’b’, and ‘c’ which represent the coefficients of the equation “ax + by = c”. His task is to find the initial integral solution of the given equation if a finite solution exists.

For example:

If ‘a’, ‘b’, and ‘c’ are 5, 10, and 10 respectively, the initial integral solution will be 2 and 0 for ‘x’ and ‘y’ respectively.

Input Format:

The first line contains an integer 'T' which denotes the number of test cases or queries to be run.

The first line of each test case contains three space-separated integers ‘a’, ‘b’, and ‘c’.

Output Format:

For each case, you need to return an array containing the value of both x and y if a finite solution exists. In case, there exists no finite solution, you can return -1 for both x and y.

The output of each test case will be printed in a separate line.

Note:

You do not need to input or print anything, and it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
1 <= a <= 100000
1 <= b <= 100000
1 <= c <= 100000

Time Limit: 1 sec

Solve now

Approaches

01 Approach

Here, we can use the extended euclidean algorithm which helps us to find the solution of a linear equation using the greatest common divisor(gcd) of the coefficients of x and y. Using this gcd, if this gcd is a divisor of ‘c’, then we can find the solution for the equation ‘ax + by = c’.

Algorithm:

Declare an array to store the solution of the linear equation
Declare two variables as ‘x’ and ‘y’ and initialize them with 0
If any of the coefficients of ‘x’ and ‘y’ is zero, we can conclude that there does not exist any finite integral solution of the linear equation.
Declare a function extendedGCD(a, b, x, y) that calculates the gcd
- If ‘b’ is equal to ‘0’
  - Set ‘x’ as ‘1’, ‘y’ as ‘0’ and return ‘a’ as the gcd
- Else
  - Calculate the gcd extendedGCD(‘b’, ‘a’ % ‘b’, ‘x’, ‘y’) and store this in a variable ‘gcd’
  - Declare two variables as ‘x1’ and ‘y1’ and set them with ‘x’ and ‘y’ respectively.
  - Set ‘x’ with ‘y1’
  - Set ‘y’ with ‘x1’ - (‘a’ / ‘b’) * ‘y1’
  - Return the ‘gcd’
Once, our gcd is calculated, if our gcd is not a divisor of ‘c’
- We do not have a solution to the equation
Else
- Put ‘x’ as ‘x’ * (‘c’ / ‘gcd’) and ‘y’ as ‘y’ * (‘c’ / ‘gcd’) in the array and return to the function.

Solve now