Linear Equation

Moderate
0/80
Average time to solve is 40m
profile
Contributed by
7 upvotes
Asked in companies
DunzoFlipkart limited

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
5 10 10
12 43 97
Sample Output 1:
2 0
1746 -485
Explanation Of Sample Input 1:
Test case 1:
For the first test case of sample output 1, for ‘a’, ‘b’ and ‘c’ as 4, 18 and 10, we get finite solution as -20 and 5 for x and y respectively.

Test case 2:   
For the second test case of sample output 1, for ‘a’, ‘b’ and ‘c’ as 12, 43 and 97, we get a finite solution as 1746 and -485 for x and y respectively.
Sample Input 2:
1
4 6 1
Sample Output 2:
-1 -1
Explanation Of Sample Input 2:
Test case 1:
For the first test case of sample output 1, for ‘a’, ‘b’ and ‘c’ as 4, 6 and 1, we get no solution. Hence, we receive -1 and -1 for x and y respectively.
Hint

Can Extended Euclidean Algorithm help us?

Approaches (1)
Mathematics

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.
Time Complexity

O(log(max(a, b))) where ‘a’ and ‘b’ are the coefficients of ‘x’ and ‘y’ respectively.


Here, we can use a function that calculates the gcd of ‘a’ and ‘b’. The gcd function has a time complexity of O(log(max( a, b))). Hence our time complexity is O(log(max(a, b))).

Space Complexity

O(1)

 

As we have used some constant variables, Hence our space complexity is O(1).

Code Solution
(100% EXP penalty)
Linear Equation
Full screen
Console