#640 Solve the Equation - Solution

Solve a given equation and return the value of 'x' in the form of a string "x=#value". The equation contains only '+', '-' operation, the variable 'x' and its coefficient. You should return "No solution" if there is no solution for the equation, or "Infinite solutions" if there are infinite solutions for the equation.

If there is exactly one solution for the equation, we ensure that the value of 'x' is an integer.

Example 1:

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

Example 2:

Input: equation = "x=x"
Output: "Infinite solutions"

Example 3:

Input: equation = "2x=x"
Output: "x=0"

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.

The key idea in #640 Solve the Equation is to parse both sides of the equation and convert them into a standard linear form. The equation contains terms with x and constant values separated by + or -. Start by splitting the equation at the = sign to process the left and right expressions independently.

While scanning each side, keep track of two values: the total coefficient of x and the total constant sum. Carefully interpret terms such as x, -x, or 2x by converting them into numeric coefficients. After parsing both sides, move all x terms to one side and constants to the other to form a simplified equation like ax = b.

Finally, determine whether the equation has a unique solution, infinite solutions, or no solution based on the resulting coefficients. Since the equation is processed with a single pass over the string, the approach is efficient and relies mainly on string parsing and simulation.

Approach	Time Complexity	Space Complexity
Single-pass string parsing and coefficient tracking	O(n)	O(1)

Solutions (4)

Balancing Equation Terms

This approach involves rearranging the equation to separate the terms involving 'x' from the constant terms. We ensure that all terms involving 'x' are on one side of the equation and all constant terms on the other side. This allows us to solve for 'x' by simplifying both sides to isolated 'x' terms versus numerical constants.

Time Complexity: O(n), where n is the length of the equation string. Space Complexity: O(1), as we use a constant amount of extra space.

Python JavaScript

1def solveEquation(equation):
2    def parse(s):
3        x_coef = 0
4        const = 0
5        num = ''
6        sign = 1
7        i = 0
8
9        while i < len(s):
10            ch = s[i]
11            if ch == '+':
12                sign = 1
13            elif ch == '-':
14                sign = -1
15            elif ch.isdigit():
16                num = ch
17                while i + 1 < len(s) and s[i + 1].isdigit():
18                    i += 1
19                    num += s[i]
20                const += sign * int(num)
21                num = ''
22            elif ch == 'x':
23                if num == '':
24                    num = '1'
25                x_coef += sign * int(num)
26                num = ''
27            i += 1
28
29        return x_coef, const
30
31    left, right = equation.split('=')
32    left_x_coef, left_const = parse(left)
33    right_x_coef, right_const = parse(right)
34
35    total_x_coef = left_x_coef - right_x_coef
36    total_const = right_const - left_const
37
38    if total_x_coef == 0:
39        if total_const == 0:
40            return 'Infinite solutions'
41        else:
42            return 'No solution'
43    else:
44        return f'x={total_const // total_x_coef}'

Explanation

We split the equation at the equal sign and process both sides to calculate the total coefficients for 'x' and any constant. By comparing these totals, we determine if the equation has no solution, infinite solutions, or exactly one solution. Parsing involves iterating through each character of the string, summing coefficients and constants.

Combining and Simplifying Terms

This approach focuses on scanning the equation and simplifying terms by combining all instances of the variable 'x' and the constant terms separately. After combining, we analyze the coefficients to deduce the solution.

Time Complexity: O(n), where n represents the number of characters in the input string. Space Complexity: O(1), since only fixed-space variables are utilized.

C#Java

1public class Solution {
2    public string SolveEquation(string equation) {
3        (int xCoefL, int constL) = ParseEquation(equation.Split('=')[0]);
4        (int xCoefR, int constR) = ParseEquation(equation.Split('=')[1]);
5
        int xCoef = xCoefL - xCoefR;
        int constant = constR - constL;

        if (xCoef == 0) {
            return constant == 0 ? "Infinite solutions" : "No solution";
        } else {
            return "x=" + (constant / xCoef).ToString();
        }
    }

    private (int, int) ParseEquation(string side) {
        int xCoef = 0, constant = 0;
        int sign = 1;
        int i = 0;
        while (i < side.Length) {
            if (side[i] == '+') {
                sign = 1;
                i++;
            } else if (side[i] == '-') {
                sign = -1;
                i++;
            }

            int val = 0;
            bool isX = false;
            if (i < side.Length && char.IsDigit(side[i])) {
                while (i < side.Length && char.IsDigit(side[i])) {
                    val = val * 10 + (side[i] - '0');
                    i++;
                }
            } else {
                val = 1;
            }

            if (i < side.Length && side[i] == 'x') {
                isX = true;
                i++;
            }

            if (isX) {
                xCoef += sign * val;
            } else {
                constant += sign * val;
            }
        }
        return (xCoef, constant);
    }
}