Leetcode 640. Solve the Equation

Problem Explanation

Given an equation, we are to determine the solution. The equation will include the variable x and may be represented in various forms such as 2x, x etc. We also have three conditions to consider:

1. If the equation has no solution, return "No solution".
2. If the equation has infinite solutions, return "Infinite solutions".
3. If there is exactly one solution, return the solution in the form: x=2.

For example, if the equation is "x+5-3+x=6+x-2", on the left side of the equation we have 2x + 2 and on the right side we have x + 4. After simplifying we get x = 2. The output will be "x=2".

Solution Approach

To determine the solution for x, we would need to analyze the equation and evaluate both sides (i.e. the left-hand side and the right-hand side). After evaluating both sides, we subtract the evaluated right-hand side from the evaluated left-hand side.

If the coefficient is zero and the constant is zero, it means there are infinite solutions to the equation. If the coefficient is zero and the constant is not zero, it means there is no solution to the equation. If the coefficient is not zero, we divide the constant by the coefficient to find the value of x.

Python Solution

1
2python
3class Solution:
4    def calculate(self, s):
5        coefficient = 0
6        constant = 0
7        num = 0
8        sign = 1
9
10        for i, c in enumerate(s):
11            if c.isdigit():
12                num = num * 10 + int(c)
13            elif c in '+-':
14                constant += sign * num
15                sign = 1 if c == '+' else -1
16                num = 0
17            else:
18                coefficient += num if num != 0 else sign
19                num = 0
20    
21        return coefficient, constant + sign * num
22
23    def solveEquation(self, equation):
24        lhs, rhs = equation.split('=')
25        lhs_coefficient, lhs_constant = self.calculate(lhs)
26        rhs_coefficient, rhs_constant = self.calculate(rhs)
27        coefficient = lhs_coefficient - rhs_coefficient
28        constant = rhs_constant - lhs_constant
29
30        if coefficient == 0 and constant == 0:
31            return "Infinite solutions"
32        elif coefficient == 0 and constant != 0:
33            return "No solution"
34        else:
35            return "x=" + str(constant // coefficient)

The calculate function analyzes each expression per side of the equation. It splits the expression into its constant and variable components. The solveEquation function then compares both sides to determine the conditions aforementioned.

Java Solution

1
2java
3class Solution {
4  public String solveEquation(String equation) {
5    String[] parts = equation.split("=");
6    int[] leftPart = evaluate(parts[0]);
7    int[] rightPart = evaluate(parts[1]);
8    int coefficient = leftPart[0] - rightPart[0];
9    int constant = rightPart[1] - leftPart[1];
10
11    if (coefficient == 0 && constant != 0) return "No solution";
12    if (coefficient == 0 && constant == 0) return "Infinite solutions";
13    return "x=" + constant / coefficient;
14  }
15
16  private int[] evaluate(String expression) {
17    int[] result = {0, 0};
18    String[] parts = expression.split("(?=[-+])");
19    for (String part : parts) {
20      if (part.equals("x") || part.equals("+x")) result[0]++;
21      else if (part.equals("-x")) result[0]--;
22      else if (part.contains("x")) result[0] += Integer.parseInt(part.replace("x", ""));
23      else result[1] += Integer.parseInt(part);
24    }
25    return result;
26  }
27}

The Java solution operates similarly to the Python solution, albeit with its respective language syntax considerations.

C++ Solution

1
2cpp
3class Solution {
4public:
5    string solveEquation(string equation) {
6        int res[2] = {0, 0}, sign = 1, coeff = 0, idx = 0, i = 0, isLeft = 1;
7        while (i < equation.size()) {
8            if (equation[i] >= '0' && equation[i] <= '9') {
9                int start = i;
10                while (i < equation.size() && equation[i] >= '0' && equation[i] <= '9') {
11                    i++;
12                }
13                coeff = stoi(equation.substr(start, i - start));
14            } else {
15                if (equation[i] == 'x') {
16                    if ((i > 0 && equation[i - 1] == '0') || (i > 1 && equation.substr(i - 2, 2) == "+0")) {
17                        idx += 0;
18                    } else {
19                        idx += (coeff != 0 ? coeff : 1) * isLeft * sign;
20                    }
21                    coeff = 0;
22                } else if (equation[i] == '+' || equation[i] == '-') {
23                    res[0] += coeff * isLeft * sign;
24                    coeff = 0;
25                    sign = (equation[i] == '+' ? 1 : -1);
26                } else if (equation[i] == '=') {
27                    res[0] += coeff * isLeft * sign;
28                    coeff = 0;
29                    sign = 1;
30                    isLeft = -1;
31                }
32                i++;
33            }
34        }
35        res[0] += coeff * isLeft * sign;
36        res[1] += idx;
37        if (res[1] == 0 && res[0] == 0)
38            return "Infinite solutions";
39        if (res[1] == 0 && res[0] != 0)
40            return "No solution";
41        return "x=" + to_string(-res[0] / res[1]);
42    }
43};

JavaScript Solution

1
2javascript
3var solveEquation = function(equation) {
4    let [left, right] = equation.split('=');
5    let leftParts = evaluate(left);
6    let rightParts = evaluate(right);
7    let lCoefficient = leftParts[0];
8    let lConstant = leftParts[1];
9    let rCoefficient = rightParts[0];
10    let rConstant = rightParts[1];
11    let coefficient = lCoefficient - rCoefficient;
12    let constant = rConstant - lConstant;
13    
14    if (coefficient === 0 && constant !== 0) return "No solution"
15    if (coefficient === 0 && constant === 0) return "Infinite solutions"
16    return `x=${constant / coefficient}`
17};
18
19var evaluate = function(expression) {
20    let parts = expression.split(/([+-])/).filter(Boolean);
21    let coefficient = 0, constant = 0;
22    parts.forEach(part => {
23        if (part.includes('x')) {
24            part = part.replace('x', '');
25            part = (part === "" || part === "+") ? 1 : (part === '-') ? -1 : parseInt(part);
26            coefficient += part;
27        } else {
28            constant += parseInt(part);
29        }
30    });
31    return [coefficient, constant];
32}

The JavaScript solution follows the same steps, using a helper function to evaluate the left and right hand sides, then comparing the results to determine the solution for x. Parts of the equation are split using regular expressions to easily isolate the coefficients and constants for calculation.

C# Solution

1
2csharp
3public class Solution {
4    public string SolveEquation(string equation) {
5        var parts = equation.Split('=');
6        var left = Evaluate(parts[0]);
7        var right = Evaluate(parts[1]);
8        var coefficient = left[0] - right[0];
9        var value = right[1] - left[1];
10
11        if (coefficient == 0 && value == 0)
12            return "Infinite solutions";
13        else if (coefficient == 0)
14            return "No solution";
15        else
16            return $"x={value/coefficient}";
17    }
18
19    private int[] Evaluate(string exp) {
20        var sign = 1;
21        int i = 0, n = exp.Length;
22        int[] res = new int[2];
23        int num = 0;
24
25        while (i < n)
26        {
27            if (exp[i] == '+')
28            {
29                i++;
30                sign = 1;
31            }
32            else if (exp[i] == '-')
33            {
34                i++;
35                sign = -1;
36            }
37            else if (char.IsDigit(exp[i]))
38            {
39                while (i < n && char.IsDigit(exp[i]))
40                {
41                    num = 10 * num + (exp[i]-'0');
42                    i++;
43                }
44                if (i < n && exp[i] == 'x')
45                {
46                    res[0] += sign * (num == 0 ? 1 : num);
47                    num = 0;
48                    i++;
49                }
50                else
51                {
52                    res[1] += sign * num;
53                    num = 0;
54                }
55            }
56            else
57            {
58                res[0] += sign;
59                i++;
60            }
61        }
62
63        res[1] += sign * num;
64        return res;
65    }
66}

Here, a similar analysis is implemented. A helper function calculates coefficients and constants from each term and equation information is compared to determine x. An integer array is used to maintain a count of coefficients and constants for each equation side.These solutions provide a comprehensive approach to solving the given equation and demonstrate how the same logic can be applied across multiple programming languages. It's always important to remember to handle every edge case, such as when there are infinite solutions or no solutions to the equation. Happy coding!

Here are few tips which can be helpful:

• Always start by understanding the problem and requirements.

• Think about different ways to solve the issue and realize the pros and cons of each method.

• Understand that there may be multiple correct answers.

• Plan your approach before you start coding.

• Test with various inputs to make sure your solution works for all cases.

• Keep practicing! Knowledge of programming concepts and problem-solving skills are improved and developed through continuous practice and learning.

• Don’t be scared of making mistakes. They are stepping stones to success.

These strategies aren't just for solving equations—they apply widely to any programming problem-solving exercises. Programming is about continuing to learn, problem solve, and persist. Keep practicing with other problems and over time, it will become easier to find the optimal solution. Happy coding!