Facebook Pixel

640. Solve the Equation

MediumMathStringSimulation
Leetcode Link

Problem Description

You're given a linear equation as a string that contains the variable x and need to solve for its value. The equation uses only + and - operations, the variable x (with or without coefficients), and constant numbers.

The equation format is: left_side = right_side, where both sides can contain terms with x and constant terms. For example:

  • "x+5-3+x=6+x-2"
  • "2x+3=x-1"
  • "x=x"

Your task is to:

  1. If there's exactly one solution: Return the value of x in the format "x=#value" where #value is an integer. For example, "x=2" or "x=-3".

  2. If there's no solution: Return "No solution". This happens when the equation simplifies to something impossible like 0 = 5.

  3. If there are infinite solutions: Return "Infinite solutions". This occurs when the equation simplifies to something always true like 0 = 0 or x = x.

The equation parsing rules:

  • Terms can be like "x", "2x", "-x", "5", "-3", etc.
  • The coefficient of x can be positive, negative, or omitted (meaning 1)
  • Constants are regular integers
  • Operations are limited to addition and subtraction

The solution approach involves:

  1. Parsing both sides of the equation to extract coefficients of x and constant terms
  2. Moving all x terms to one side and constants to the other: (x1 - x2) * x = (y2 - y1)
  3. Checking if a unique solution exists based on the coefficients
  4. Calculating the solution when it exists
Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

When solving a linear equation algebraically, we typically move all terms containing x to one side and all constant terms to the other side. This is exactly what we need to simulate programmatically.

Think about how you'd solve 2x + 3 = x - 1 by hand:

  1. You'd move all x terms to the left: 2x - x = -1 - 3
  2. Simplify: x = -4

The key insight is that any linear equation can be represented as ax + b = cx + d, where:

  • a is the total coefficient of x on the left side
  • b is the sum of constants on the left side
  • c is the total coefficient of x on the right side
  • d is the sum of constants on the right side

Rearranging algebraically: ax - cx = d - b, which gives us (a - c)x = d - b.

This leads to three possible cases:

  1. If a - c ≠ 0: We can divide both sides by (a - c) to get x = (d - b) / (a - c). This gives us a unique solution.

  2. If a - c = 0 and d - b = 0: The equation becomes 0 = 0, which is always true regardless of x. This means infinite solutions.

  3. If a - c = 0 but d - b ≠ 0: The equation becomes 0 = some_non_zero_number, which is impossible. This means no solution.

The parsing strategy follows naturally: we need to scan through each side of the equation, identifying whether each term is a coefficient of x or a constant, keeping track of signs (+ or -). A term ending with x contributes to the coefficient sum, while a pure number contributes to the constant sum.

Learn more about Math patterns.

Solution Approach

The implementation uses a helper function f(s) to parse each side of the equation and extract the coefficients of x and the constant terms.

Parsing Function f(s):

  1. Initialize counters: x = 0 for the total coefficient of x, and y = 0 for the sum of constants.

  2. Normalize the string: If the string doesn't start with a sign, prepend '+' to make parsing uniform. This ensures every term starts with either '+' or '-'.

  3. Iterate through the string: Use two pointers i and j:

    • i points to the current sign ('+' or '-')
    • j scans ahead to find the next sign or end of string
    • Extract the substring v = s[i:j] which represents one term

  4. Process each term:

    • Determine the sign: sign = 1 for '+', sign = -1 for '-'
    • Check if the term ends with 'x':
      • If yes, it's an x term. Extract coefficient:
        • If v is just "x" (length 1), coefficient is 1
        • Otherwise, parse the number before 'x' as the coefficient
        • Add sign * coefficient to x
      • If no, it's a constant term:
        • Parse the entire term as an integer
        • Add sign * value to y

Main Algorithm:

  1. Split the equation: Use equation.split('=') to get left side a and right side b.

  2. Parse both sides:

    • x1, y1 = f(a) gives coefficients and constants from the left side
    • x2, y2 = f(b) gives coefficients and constants from the right side

  3. Solve the equation:

    • After rearranging: (x1 - x2) * x = (y2 - y1)

  4. Determine the solution type:

    • If x1 == x2:
      • If y1 == y2: The equation becomes 0 = 0 → "Infinite solutions"
      • If y1 != y2: The equation becomes 0 = non_zero → "No solution"
    • If x1 != x2:
      • Calculate x = (y2 - y1) // (x1 - x2) using integer division
      • Return the result as f'x={value}'

Example walkthrough for "2x+3=x-1":

  • Left side: x1 = 2, y1 = 3
  • Right side: x2 = 1, y2 = -1
  • Since x1 ≠ x2: x = (-1 - 3) // (2 - 1) = -4 // 1 = -4
  • Result: "x=-4"

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through solving the equation "x+5-3+x=6+x-2" step by step.

Step 1: Split the equation

  • Left side: "x+5-3+x"
  • Right side: "6+x-2"

Step 2: Parse the left side "x+5-3+x"

Since it doesn't start with a sign, we prepend '+': "+x+5-3+x"

Now we iterate through and extract terms:

  • Start at position 0 ('+'), scan to position 2 (next '+'): term is "+x"

    • Sign: + (so multiply by 1)
    • Ends with 'x' and length is 1, so coefficient = 1
    • Add 1 to x coefficient: x1 = 1

  • Start at position 2 ('+'), scan to position 4 (next '-'): term is "+5"

    • Sign: + (so multiply by 1)
    • Doesn't end with 'x', so it's a constant = 5
    • Add 5 to constants: y1 = 5

  • Start at position 4 ('-'), scan to position 6 (next '+'): term is "-3"

    • Sign: - (so multiply by -1)
    • Doesn't end with 'x', so it's a constant = 3
    • Add -3 to constants: y1 = 5 + (-3) = 2

  • Start at position 6 ('+'), scan to end: term is "+x"

    • Sign: + (so multiply by 1)
    • Ends with 'x' and length is 1, so coefficient = 1
    • Add 1 to x coefficient: x1 = 1 + 1 = 2

Left side result: x1 = 2, y1 = 2

Step 3: Parse the right side "6+x-2"

Prepend '+': "+6+x-2"

Extract terms:

  • "+6": constant, add 6 to y2 = 6
  • "+x": x term with coefficient 1, add 1 to x2 = 1
  • "-2": constant, add -2 to y2 = 6 + (-2) = 4

Right side result: x2 = 1, y2 = 4

Step 4: Solve the equation

We have the equation in the form: (x1 - x2) * x = (y2 - y1)

Substituting our values: (2 - 1) * x = (4 - 2)

This simplifies to: 1 * x = 2

Step 5: Determine the solution

Since x1 - x2 = 1 ≠ 0, we have a unique solution:

  • x = (y2 - y1) / (x1 - x2) = 2 / 1 = 2

Final Answer: "x=2"

To verify: substituting x=2 into the original equation:

  • Left side: 2 + 5 - 3 + 2 = 6
  • Right side: 6 + 2 - 2 = 6
  • Both sides equal 6 ✓

Solution Implementation

1class Solution:
2    def solveEquation(self, equation: str) -> str:
3        def parse_expression(expression: str) -> tuple[int, int]:
4            """
5            Parse an expression and return coefficients of x and constant terms.
6          
7            Args:
8                expression: String representing one side of the equation
9          
10            Returns:
11                Tuple of (x_coefficient, constant_term)
12            """
13            x_coefficient = 0
14            constant_term = 0
15          
16            # Add leading '+' if expression doesn't start with a sign
17            if expression[0] != '-':
18                expression = '+' + expression
19          
20            i = 0
21            n = len(expression)
22          
23            while i < n:
24                # Determine the sign of current term
25                sign = 1 if expression[i] == '+' else -1
26                i += 1
27              
28                # Find the end of current term
29                j = i
30                while j < n and expression[j] not in '+-':
31                    j += 1
32              
33                # Extract the current term
34                term = expression[i:j]
35              
36                # Process the term based on whether it contains 'x'
37                if term[-1] == 'x':
38                    # Term is a coefficient of x
39                    if len(term) > 1:
40                        # Extract coefficient before 'x'
41                        x_coefficient += sign * int(term[:-1])
42                    else:
43                        # Just 'x' means coefficient is 1
44                        x_coefficient += sign * 1
45                else:
46                    # Term is a constant
47                    constant_term += sign * int(term)
48              
49                # Move to next term
50                i = j
51          
52            return x_coefficient, constant_term
53      
54        # Split equation into left and right sides
55        left_side, right_side = equation.split('=')
56      
57        # Parse both sides of the equation
58        left_x_coeff, left_const = parse_expression(left_side)
59        right_x_coeff, right_const = parse_expression(right_side)
60      
61        # Rearrange equation to form: (left_x - right_x) * x = right_const - left_const
62        final_x_coeff = left_x_coeff - right_x_coeff
63        final_const = right_const - left_const
64      
65        # Check for special cases
66        if final_x_coeff == 0:
67            # No x terms after simplification
68            if final_const == 0:
69                # 0 = 0, any x is a solution
70                return 'Infinite solutions'
71            else:
72                # 0 = non-zero, no solution exists
73                return 'No solution'
74      
75        # Normal case: solve for x
76        x_value = final_const // final_x_coeff
77        return f'x={x_value}'
78
1class Solution {
2    /**
3     * Solves a linear equation with one variable 'x'.
4     * The equation is in the form "left_side=right_side".
5     * 
6     * @param equation The equation string to solve
7     * @return The solution: "x=value", "Infinite solutions", or "No solution"
8     */
9    public String solveEquation(String equation) {
10        // Split the equation into left and right sides
11        String[] sides = equation.split("=");
12      
13        // Parse both sides to get coefficients
14        // Each side returns [coefficient of x, constant term]
15        int[] leftSide = parseExpression(sides[0]);
16        int[] rightSide = parseExpression(sides[1]);
17      
18        // Extract coefficients and constants
19        int leftXCoefficient = leftSide[0];
20        int leftConstant = leftSide[1];
21        int rightXCoefficient = rightSide[0];
22        int rightConstant = rightSide[1];
23      
24        // Rearrange equation: (leftX - rightX) * x = rightConstant - leftConstant
25        // Check if coefficients of x are equal (no x terms after simplification)
26        if (leftXCoefficient == rightXCoefficient) {
27            // If constants are also equal, any x satisfies the equation
28            // If constants are different, no solution exists
29            return leftConstant == rightConstant ? "Infinite solutions" : "No solution";
30        }
31      
32        // Calculate x value: x = (rightConstant - leftConstant) / (leftXCoefficient - rightXCoefficient)
33        return "x=" + (rightConstant - leftConstant) / (leftXCoefficient - rightXCoefficient);
34    }
35
36    /**
37     * Parses an expression string and extracts coefficients.
38     * 
39     * @param expression The expression to parse (e.g., "2x+3", "-x-5")
40     * @return An array with [coefficient of x, constant term]
41     */
42    private int[] parseExpression(String expression) {
43        int xCoefficient = 0;  // Total coefficient of x terms
44        int constantTerm = 0;   // Total of constant terms
45      
46        // Add leading '+' if expression doesn't start with a sign
47        if (expression.charAt(0) != '-') {
48            expression = "+" + expression;
49        }
50      
51        int currentIndex = 0;
52        int length = expression.length();
53      
54        // Process each term in the expression
55        while (currentIndex < length) {
56            // Determine the sign of current term
57            int sign = expression.charAt(currentIndex) == '+' ? 1 : -1;
58            currentIndex++;
59          
60            // Find the end of current term (next '+' or '-' or end of string)
61            int termEndIndex = currentIndex;
62            while (termEndIndex < length && 
63                   expression.charAt(termEndIndex) != '+' && 
64                   expression.charAt(termEndIndex) != '-') {
65                termEndIndex++;
66            }
67          
68            // Extract the current term
69            String term = expression.substring(currentIndex, termEndIndex);
70          
71            // Check if this is an x term or a constant
72            if (expression.charAt(termEndIndex - 1) == 'x') {
73                // This is an x term
74                // If term is just "x", coefficient is 1; otherwise parse the coefficient
75                int coefficient;
76                if (term.length() > 1) {
77                    // Extract coefficient (remove 'x' from the end)
78                    coefficient = Integer.parseInt(term.substring(0, term.length() - 1));
79                } else {
80                    // Term is just "x", so coefficient is 1
81                    coefficient = 1;
82                }
83                xCoefficient += sign * coefficient;
84            } else {
85                // This is a constant term
86                constantTerm += sign * Integer.parseInt(term);
87            }
88          
89            // Move to next term
90            currentIndex = termEndIndex;
91        }
92      
93        return new int[] {xCoefficient, constantTerm};
94    }
95}
96
1#include <string>
2#include <sstream>
3#include <utility>
4
5class Solution {
6public:
7    /**
8     * Solves a linear equation in the form "ax + b = cx + d"
9     * Returns the value of x, "No solution", or "Infinite solutions"
10     */
11    std::string solveEquation(std::string equation) {
12        // Find the position of '=' to split the equation
13        size_t equalPos = equation.find('=');
14        std::string leftSide = equation.substr(0, equalPos);
15        std::string rightSide = equation.substr(equalPos + 1);
16      
17        // Parse both sides of the equation
18        auto leftCoefficients = parseExpression(leftSide);
19        auto rightCoefficients = parseExpression(rightSide);
20      
21        // Extract coefficients for clarity
22        int leftXCoeff = leftCoefficients.first;
23        int leftConstant = leftCoefficients.second;
24        int rightXCoeff = rightCoefficients.first;
25        int rightConstant = rightCoefficients.second;
26      
27        // Check for special cases
28        if (leftXCoeff == rightXCoeff) {
29            // Same x coefficients on both sides
30            if (leftConstant != rightConstant) {
31                // Contradiction: e.g., 3 = 5
32                return "No solution";
33            }
34            // Identity: e.g., 3 = 3
35            return "Infinite solutions";
36        }
37      
38        // Solve for x: (leftXCoeff - rightXCoeff)x = rightConstant - leftConstant
39        int xValue = (rightConstant - leftConstant) / (leftXCoeff - rightXCoeff);
40        return "x=" + std::to_string(xValue);
41    }
42  
43private:
44    /**
45     * Parses an expression string and extracts coefficients
46     * @param expression - Mathematical expression string (e.g., "2x+3")
47     * @returns Pair of [xCoefficient, constantTerm]
48     */
49    std::pair<int, int> parseExpression(const std::string& expression) {
50        int xCoefficient = 0;      // Coefficient of x terms
51        int constantTerm = 0;       // Sum of constant terms
52        int digitCount = 0;         // Number of digits in current number
53        int sign = 1;               // Current sign (1 for positive, -1 for negative)
54        int currentNumber = 0;      // Current number being parsed
55        bool isXTerm = false;       // Whether current term contains x
56      
57        for (char ch : expression) {
58            if (ch == '+' || ch == '-') {
59                // Process the previous term when encountering a new operator
60                if (isXTerm) {
61                    // Handle coefficient for x term (default to 1 if no digits)
62                    if (digitCount == 0 && currentNumber == 0) {
63                        currentNumber = 1;
64                    }
65                    xCoefficient += currentNumber * sign;
66                } else if (digitCount > 0) {
67                    // Add constant term only if there were digits
68                    constantTerm += currentNumber * sign;
69                }
70              
71                // Reset for next term
72                isXTerm = false;
73                currentNumber = 0;
74                digitCount = 0;
75                sign = (ch == '+') ? 1 : -1;
76              
77            } else if (ch == 'x') {
78                // Mark current term as containing x
79                isXTerm = true;
80              
81            } else {
82                // Parse digit and build current number
83                digitCount++;
84                currentNumber = currentNumber * 10 + (ch - '0');
85            }
86        }
87      
88        // Process the last term after loop ends
89        if (isXTerm) {
90            // Handle coefficient for x term (default to 1 if no digits)
91            if (digitCount == 0 && currentNumber == 0) {
92                currentNumber = 1;
93            }
94            xCoefficient += currentNumber * sign;
95        } else if (digitCount > 0) {
96            // Add constant term only if there were digits
97            constantTerm += currentNumber * sign;
98        }
99      
100        return std::make_pair(xCoefficient, constantTerm);
101    }
102};
103
1/**
2 * Solves a linear equation in the form "ax + b = cx + d"
3 * Returns the value of x, "No solution", or "Infinite solutions"
4 */
5function solveEquation(equation: string): string {
6    // Split equation into left and right sides
7    const [leftSide, rightSide] = equation.split('=');
8  
9    /**
10     * Parses an expression string and extracts coefficients
11     * @param expression - Mathematical expression string (e.g., "2x+3")
12     * @returns Tuple of [xCoefficient, constantTerm]
13     */
14    const parseExpression = (expression: string): [number, number] => {
15        let xCoefficient = 0;      // Coefficient of x terms
16        let constantTerm = 0;       // Sum of constant terms
17        let digitCount = 0;         // Number of digits in current number
18        let sign = 1;               // Current sign (1 for positive, -1 for negative)
19        let currentNumber = 0;      // Current number being parsed
20        let isXTerm = false;        // Whether current term contains x
21      
22        for (const char of expression) {
23            if (char === '+' || char === '-') {
24                // Process the previous term when encountering a new operator
25                if (isXTerm) {
26                    // Handle coefficient for x term (default to 1 if no digits)
27                    if (digitCount === 0 && currentNumber === 0) {
28                        currentNumber = 1;
29                    }
30                    xCoefficient += currentNumber * sign;
31                } else {
32                    // Add constant term
33                    constantTerm += currentNumber * sign;
34                }
35              
36                // Reset for next term
37                isXTerm = false;
38                currentNumber = 0;
39                digitCount = 0;
40                sign = (char === '+') ? 1 : -1;
41              
42            } else if (char === 'x') {
43                // Mark current term as containing x
44                isXTerm = true;
45              
46            } else {
47                // Parse digit and build current number
48                digitCount++;
49                currentNumber = currentNumber * 10 + Number(char);
50            }
51        }
52      
53        // Process the last term after loop ends
54        if (isXTerm) {
55            // Handle coefficient for x term (default to 1 if no digits)
56            if (digitCount === 0 && currentNumber === 0) {
57                currentNumber = 1;
58            }
59            xCoefficient += currentNumber * sign;
60        } else {
61            // Add constant term
62            constantTerm += currentNumber * sign;
63        }
64      
65        return [xCoefficient, constantTerm];
66    };
67  
68    // Parse both sides of the equation
69    const leftCoefficients = parseExpression(leftSide);
70    const rightCoefficients = parseExpression(rightSide);
71  
72    // Extract coefficients for clarity
73    const leftXCoeff = leftCoefficients[0];
74    const leftConstant = leftCoefficients[1];
75    const rightXCoeff = rightCoefficients[0];
76    const rightConstant = rightCoefficients[1];
77  
78    // Check for special cases
79    if (leftXCoeff === rightXCoeff) {
80        // Same x coefficients on both sides
81        if (leftConstant !== rightConstant) {
82            // Contradiction: e.g., 3 = 5
83            return 'No solution';
84        }
85        // Identity: e.g., 3 = 3
86        return 'Infinite solutions';
87    }
88  
89    // Solve for x: (leftXCoeff - rightXCoeff)x = rightConstant - leftConstant
90    const xValue = (leftConstant - rightConstant) / (rightXCoeff - leftXCoeff);
91    return `x=${xValue}`;
92}
93

Time and Space Complexity

Time Complexity: O(n) where n is the length of the equation string.

The algorithm processes the equation string in the following steps:

  • The split('=') operation takes O(n) time to traverse the string and split it into two parts
  • The helper function f(s) is called twice (once for each side of the equation)
  • Inside f(s), there's a single while loop that iterates through each character of the input substring exactly once
  • String slicing operations s[i:j] take O(j-i) time, but since each character is only included in one slice throughout the entire execution, the total time for all slicing operations is O(n)
  • Other operations inside the loop (comparisons, arithmetic operations, string checks) are all O(1)

Since we traverse the entire equation string a constant number of times, the overall time complexity is O(n).

Space Complexity: O(n)

The space usage includes:

  • The split operation creates two new strings a and b, which together contain all characters from the original equation (minus the '=' character), using O(n) space
  • The helper function f(s) creates temporary string slices v = s[i:j], but at most one slice exists at any time with maximum length O(n)
  • Variables x, y, i, j, sign, x1, y1, x2, y2 use O(1) space
  • The final returned string is at most O(log n) characters (representing the numerical solution)

The dominant space usage comes from storing the split strings, resulting in O(n) space complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Parsing of Negative Coefficients

One major pitfall is mishandling terms like "-x" or when the equation starts with a negative term. The parser might incorrectly interpret the coefficient or fail to handle the sign properly.

Problem Example:

  • Input: "-x+2=3x-4"
  • The term "-x" could be parsed incorrectly if not careful about sign handling

Solution: Ensure the parsing function correctly handles:

  • Terms starting with negative signs
  • The special case where "-x" should be interpreted as coefficient -1
  • Prepending '+' only when the expression doesn't start with '-'

2. Missing Edge Cases for Coefficient Extraction

The code might fail when encountering terms like "0x", "-0x", or when there's no explicit coefficient before 'x'.

Problem Example:

  • "0x+5=5" should recognize that the coefficient of x is 0
  • "+x" or "-x" need special handling since there's no explicit number

Solution:

if term[-1] == 'x':
    if len(term) > 1:
        coeff_str = term[:-1]
        # Handle special case where coefficient is just '+' or '-'
        if coeff_str == '' or coeff_str == '+':
            x_coefficient += sign * 1
        elif coeff_str == '-':
            x_coefficient += sign * -1
        else:
            x_coefficient += sign * int(coeff_str)
    else:
        x_coefficient += sign * 1

3. Integer Division Truncation Issues

Using integer division (//) can lead to incorrect results when the solution should be a fraction. The problem states the answer should be an integer, but during development/testing, non-integer solutions might indicate parsing errors.

Problem Example:

  • If the equation "2x=3" appears, 3 // 2 = 1 would give wrong answer
  • This might hide bugs in the parsing logic

Solution: Add validation to ensure the division is exact:

if final_const % final_x_coeff != 0:
    # This shouldn't happen with valid test cases
    # But helps catch parsing errors during development
    raise ValueError("Non-integer solution detected")
x_value = final_const // final_x_coeff

4. Malformed Input Handling

The code assumes well-formed input but might crash on edge cases like:

  • Empty terms: "x+=2" (double operators)
  • Missing equals sign: "x+2"
  • Multiple equals signs: "x=2=3"

Solution: Add input validation:

if '=' not in equation or equation.count('=') != 1:
    raise ValueError("Invalid equation format")
  
# Also check for empty sides
left_side, right_side = equation.split('=')
if not left_side or not right_side:
    raise ValueError("Empty equation side")

5. Sign Handling at String Boundaries

The current approach of prepending '+' might cause issues if not carefully implemented, especially with the indexing logic.

Problem Example:

  • After prepending '+', the indices need to be adjusted correctly
  • The loop termination condition must account for the modified string length

Solution: Be explicit about the normalization step and ensure consistent handling:

def parse_expression(expression: str) -> tuple[int, int]:
    # Normalize: ensure expression starts with a sign
    if expression and expression[0] not in '+-':
        expression = '+' + expression
  
    terms = []
    current_term = ''
  
    for char in expression:
        if char in '+-' and current_term:
            terms.append(current_term)
            current_term = char
        else:
            current_term += char
  
    if current_term:
        terms.append(current_term)
  
    # Now process each complete term...

This approach separates term extraction from processing, making the logic clearer and less error-prone.

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

A heap is a ...?

Recommended Readings

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More