#640

Medium

LeetCode Problem Workspace

Solve the Equation

Solve the equation for the variable 'x' and determine its value or state if there is no solution or infinite solutions.

Problem Statement

Given an equation in the form of a string, solve for the variable 'x'. The equation will involve the addition and subtraction of integers, and the variable 'x'. You need to determine the value of 'x' or return specific outputs when there are no solutions or infinite solutions.

For equations with exactly one solution, return the result as "x=#value". If there is no solution, return "No solution", and if there are infinite solutions, return "Infinite solutions".

Examples

Example 1

Input: equation = "x+5-3+x=6+x-2"

Output: "x=2"

Example details omitted.

Example 2

Input: equation = "x=x"

Output: "Infinite solutions"

Example details omitted.

Example 3

Input: equation = "2x=x"

Output: "x=0"

Example details omitted.

Constraints

3 <= equation.length <= 1000
equation has exactly one '='.
equation consists of integers with an absolute value in the range [0, 100] without any leading zeros, and the variable 'x'.
The input is generated that if there is a single solution, it will be an integer.

Solution Approach

Parse the Equation

Start by splitting the equation at the equals sign to create two parts. Each part will be processed separately to isolate terms involving 'x' on one side and constants on the other.

Balance the Equation

Convert all terms to one side of the equation, ensuring that terms involving 'x' are grouped together, and constants are isolated. Use basic arithmetic to move terms across the equals sign.

Solve for 'x'

After balancing, calculate the value of 'x' by dividing the sum of constants by the coefficient of 'x'. If the equation results in contradictions or identities, determine if there is no solution or infinite solutions.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time and space complexity depend on how you process the equation. Parsing the string and performing arithmetic operations both involve linear time complexity, O(n), where n is the length of the equation. Space complexity depends on how the equation is stored and split, typically O(n).

What Interviewers Usually Probe

Look for candidates who can break down and parse the string effectively.
Evaluate how well they handle edge cases, such as infinite solutions or no solutions.
Assess if they can balance the equation systematically and solve for 'x' without skipping steps.

Common Pitfalls or Variants

Common pitfalls

Overcomplicating the parsing process, leading to errors when extracting coefficients or constants.
Failing to account for edge cases, such as when the equation simplifies to 'x=x' (infinite solutions).
Mismanaging signs during the balancing step, which could lead to incorrect values for 'x'.

Follow-up variants

Equations with only addition or subtraction operations.
Handling more complex terms such as fractions or higher powers of 'x'.
Expanding the problem to handle multiple variables or more complicated expressions.

FAQ

How do I solve equations in the form 'x=5'?

Simply return the solution as 'x=5'. The equation is already balanced, so no further steps are necessary.

What if there is no 'x' in the equation?

If there is no 'x' and the constants do not balance, return 'No solution'. If the equation is always true, return 'Infinite solutions'.

What happens when the equation simplifies to 'x=x'?

This equation has infinite solutions. Return 'Infinite solutions' as the result.

Can the input equation contain terms with multiple variables?

No, this problem specifically deals with equations containing only one variable, 'x'.

How does GhostInterview help with solving this problem?

GhostInterview offers step-by-step assistance for parsing and balancing the equation, ensuring you handle all special cases, such as infinite or no solutions.

terminal

Solution

Solution 1: Mathematics

We split the $equation$ by the equal sign `"="` into left and right expressions, and compute the coefficient of `"x"` (denoted $x_i$) and the constant value (denoted $y_i$) for each side.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

class Solution:
    def solveEquation(self, equation: str) -> str:
        def f(s):
            x = y = 0
            if s[0] != '-':
                s = '+' + s
            i, n = 0, len(s)
            while i < n:
                sign = 1 if s[i] == '+' else -1
                i += 1
                j = i
                while j < n and s[j] not in '+-':
                    j += 1
                v = s[i:j]
                if v[-1] == 'x':
                    x += sign * (int(v[:-1]) if len(v) > 1 else 1)
                else:
                    y += sign * int(v)
                i = j
            return x, y

        a, b = equation.split('=')
        x1, y1 = f(a)
        x2, y2 = f(b)
        if x1 == x2:
            return 'Infinite solutions' if y1 == y2 else 'No solution'
        return f'x={(y2 - y1) // (x1 - x2)}'

Continue Practicing

#592 fraction addition and subtraction #537 complex number multiplication #415 add strings