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:
- If the equation has no solution, return "No solution".
- If the equation has infinite solutions, return "Infinite solutions".
- 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!
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.