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 <= 1000equation has exactly one '='.equation consists of integers with an absolute value in the range [0, 100] without any leading zeros, and the variable 'x'.Problem Overview: The input is a string representing a linear equation such as x+5-3+x=6+x-2. Your job is to isolate x and return the solution in the form x=#value. If both sides reduce to the same expression, the result is Infinite solutions. If the equation becomes contradictory, return No solution.
Approach 1: Balancing Equation Terms (O(n) time, O(1) space)
Split the equation into left and right parts using the = sign. Parse each side character by character and track two values: the coefficient of x and the constant sum. When you encounter a term like 2x, update the coefficient; when you encounter a number like 5, update the constant. After processing both sides, move all x terms to one side and constants to the other by subtracting coefficients and constants appropriately.
This effectively “balances” the equation: ax + b = cx + d becomes (a - c)x = d - b. If the resulting coefficient of x is zero, check whether the constants are equal to determine infinite or no solutions. The implementation relies on careful string parsing and sign tracking, which makes it a practical exercise in string processing combined with simple math operations.
Approach 2: Combining and Simplifying Terms (O(n) time, O(1) space)
Instead of handling left and right sides separately, scan the entire equation once and normalize the terms while traversing. Track the current sign and switch behavior when crossing the = symbol. Terms before = contribute normally; terms after it contribute with inverted signs because they conceptually move to the left side.
For each token, determine whether it is an x term or a numeric constant. Maintain two accumulators: total coefficient of x and total constant value. For example, encountering +3x adds 3 to the coefficient, while -5 subtracts 5 from the constant. When the scan completes, the equation reduces to ax + b = 0. Solving becomes straightforward: compute x = -b / a, with special handling when a == 0.
This method treats the equation as a single stream of tokens and uses a lightweight simulation of algebraic term movement. It avoids storing intermediate lists of tokens and keeps the logic compact.
Recommended for interviews: Interviewers usually expect the linear scan that aggregates coefficients and constants. It demonstrates comfort with string parsing and algebraic simplification in O(n) time and O(1) space. Implementing the balanced two-side parsing first can help reason about the equation structure, but the single-pass simplification shows stronger problem-solving efficiency.
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.
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.
Python
JavaScript
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.
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.
In this C# solution, we further enhance parsing by leveraging tuples for clean coefficient and constant extraction. This method helps standardize processing by treating everything as terms to be added or subtracted from a total, revealing a systematic deduction path for solutions or infinite cases.
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.
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.
The equation is then transformed into: x_1 times x + y_1 = x_2 times x + y_2.
x_1 = x_2: if y_1 neq y_2, there is no solution; if y_1 = y_2, there are infinite solutions.x_1 neq x_2: there is a unique solution x = \frac{y_2 - y_1}{x_1 - x_2}.Similar problems:
Python
Java
Go
TypeScript
| Approach | Complexity |
|---|---|
| Balancing Equation Terms | 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. |
| Combining and Simplifying Terms | 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. |
| Mathematics | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Balancing Equation Terms | O(n) | O(1) | Good when you want clear separation of left and right expressions before solving |
| Combining and Simplifying Terms (Single Pass) | O(n) | O(1) | Preferred interview solution; processes the equation in one scan with minimal state |
LeetCode 640. Solve the Equation Explantion and Solution • happygirlzt • 1,978 views views
Watch 6 more video solutions →Practice Solve the Equation with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor