Nobita’s Assignment

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
9 upvotes
Asked in company
314e Corporation

Problem statement

Nobita has got math assignment to solve. In this assignment, he has to solve a mathematical equation given in the form of a string 'S'. The equation contains only ‘+’ and ‘-’ operators and a variable ‘x’. Nobita doesn’t know how to solve the equation. So, he went to Doremon for help. Doremon gives him a gadget for this. But as usual, Nobita didn’t listen to the instructions to use that gadget.

So, now it's your task to help Nobita find solutions to the given equation, or if there is no solution, report that as well.

Note : 
If there is no solution for the equation, return "No solution.”

If there is only one solution for the equation, return that solution for ‘x.’

If there are infinite solutions for the equation, return "Infinite solutions.”

‘x’ may or may not have coefficients associated with it.

‘+’, ‘-’, and ‘x’ can occur any number of times in the equation.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer ‘T’ representing the number of test cases.

The next ‘T’ lines contain a string ‘S’ representing the equation given to Nobita.
Output Format : 
For each test case, print the value of ‘x’, and if the solution doesn’t exist, then print “No solution,” and if there are infinite solutions, then print “Infinite solutions”.

Output for every test case will be printed in a separate line.
Note : 
You don’t need to print anything; It has already been taken care of.
Constraints : 
1 <= T <= 50
3 <= |S| <= 10^7
-100 <= y <= 100

Time limit: 1 sec
Sample Input 1 :
2
x+4=5
x=x
Sample Output 1 :
1
Infinite solutions
Explanation For Sample Input 1 :
In test case 1, after shifting 4 from LHS to RHS equation becomes “x = 5 - 4” for which
“x = 1.”

In test case 2, there are infinite values possible for which ‘x’ will be equal to ‘x’. Hence there will be infinite solutions.
Sample input 2 :
2
x=x+5
x+6=0
Sample output 2 :
No solution 
-6
Hint

Can you think of a solution using the property of mathematical equations?

Approaches (1)
Partitioning LHS and RHS

Each constant and each variable have a corresponding sign to them ‘+’ or ‘-’. So divide the string into two partitions; all that comes before “=” is LHS and after “=” is treated as RHS. Then exclusively use the property of shifting from LHS to RHS or vice versa to solve the equation.

 

The steps are as follows:

 

  • Declare a  variable ‘FLAG’ for partition logic. This variable will be of type int and declare it with 1 initially.
  • Declare two variables ‘CONSTANT' = 0 and ‘COEFF' = 0 of type int to store resultant constants and coefficients sum from both LHS and RHS.
  • Iterate over the equation string ‘S’ (say iterator be ‘i’)
    • Declare a variable ‘SIGN’ of type int.
    • If ‘S[i]’  is equal to ‘=’ then change the ‘FLAG’ to -1.
    • Else If ‘S[i]’ is equal to ‘+’ then change ‘SIGN’ to 1.
    • If ‘S[i]’ is equal to ‘-’ then change ‘SIGN’ to -1.
    • Move iterator ‘i’ to find if we have a variable next to the current sign or a digit.
      • If there is a Digit, move ‘i’ till you find the complete number:
    • Store the number in ‘TEMP.’
    • If ‘S[i]’ == ’x’:
      • Increment ‘COEFF’ by ‘FLAG’ * ‘TEMP’ * ‘SIGN’
    • Else:
      • Increment ‘CONSTANT’ by ‘FLAG’ * ‘TEMP’ * ‘SIGN’.
    • Else if there is Variable ‘x’: Increment ‘COEFF’ by ‘FLAG’ * ‘SIGN.’
  • If the total sum of coefficients from both LHS and RHS and the total sum of constants from both LHS and RHS is 0, i.e., ‘CONSTANT’ == 0 and ‘COEFF’ == 0, in that case, return “Infinite Solutions”.
  • If the total sum of the coefficient from both LHS and RHS is 0, and the total sum of constants from both LHS and RHS is non zero, i.e., ‘COEFF’ == 0 and ‘CONSTANT’ != 0; in that case return “No Solution.”
  • In all other cases, return the string of a single solution hence deduced.

 

Time Complexity

O(|S|), where |S| is the size of the given string ‘S’.

 

We iterate over the string to create total constants and coefficient sum for both LHS and RHS. Hence the overall time complexity is O(|S|).

Space Complexity

O(1)

 

Constant extra space is used.

Code Solution
(100% EXP penalty)
Nobita’s Assignment
Full screen
Console