640. Solve the Equation

MediumMathStringSimulation
Leetcode Link

Problem Description

The problem asks us to solve a linear algebraic equation for the variable x and to return the solution as a string in the format "x=#value". An algebraic equation is a mathematical statement that uses constants, variables (in this case, x), and arithmetic operations (addition and subtraction) to set two expressions equal to each other. The given equation will only contain these operations and the variable x with a possible coefficient (a number multiplying the variable).

The task involves three potential outcomes:

  1. There is exactly one solution to the equation. The problem assures us that if this is the case, the value of 'x' will be an integer, and we should return it in the specified format.

  2. There is no solution to the equation. If the terms involving the variable x cancel each other out, but the constant terms do not, this means the equation is contradictory (for example, "0x=3" has no solution), and we should return "No solution".

  3. There are infinite solutions to the equation. If both the variable terms and the constant terms cancel out, the equation is true for all values of x (for example, "0x=0"), and we should return "Infinite solutions".

Intuition

To solve the equation, we can first split it into two parts, the left-hand side (LHS) and the right-hand side (RHS), at the equals sign ('='). Each side will be evaluated independently to simplify the equation to determine the x term's coefficient and the constant term.

The core intuition behind the solution involves these steps:

  1. Separating each term: We iterate through each character of the equation string. Every time we encounter a '+' or '-', we know that a new term is starting. A term can be a coefficient of x (like "2x", "-3x", or "+x") or just a constant (like "5" or "-6").

  2. Interpret each term: For each term, we need to decide if it contains x or not. If it does, we extract the coefficient; if it's just a number, we handle it as a constant term. The coefficient of x can be potentially positive or negative, which is indicated by the sign immediately preceding the term. We take this sign into account when adding to the total coefficient of x.

  3. Consolidating terms: After translating all terms on one side of the equation into their numeric values (with the appropriate signs), we sum up all the x coefficients to get the net coefficient of x for one side, and we sum up all the constants to get the net constant for that side.

  4. Equating and Simplifying: After we have the net x coefficient and constant for both the LHS and RHS, we can consolidate the equation such that all x terms are on one side and all constant terms are on the other side. This is done by subtracting the x coefficients and constant terms of one side from the other.

  5. Solving for x: If the net x coefficient is not zero, we can solve for x by dividing the net constants' difference by the net x coefficients' difference. This will give us the value of x.

  6. Determining the Outcome: We check the net coefficients to see if there is one solution, no solution, or infinite solutions. If the net coefficient of x is zero and the constants are equal, there are infinite solutions. If the net coefficient of x is zero and the constants are not equal, there is no solution. Otherwise, we return the calculated value of x.

Learn more about Math patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

How does quick sort divide the problem into subproblems?

Solution Approach

The implementation of the solution follows a systematic approach to separately interpret the left-hand side and right-hand side of the equation, extract the coefficients of x and the constant terms, subsequently process them, and finally evaluate the required solution (if it exists).

The solveEquation function is the entry point of the solution. It receives the equation as an input string. It begins by defining an inner function f(s) that takes one side of the equation (as a string s) and performs the extraction and summation of x coefficients and constants.

Inner Function f(s)

  1. Initialization: Two variables x and y are initialized to 0. Here, x will hold the sum of the coefficients of x and y will hold the sum of the constant terms.

  2. Handling Signage: If the string does not start with a minus sign ('-'), a plus sign ('+') is prepended to ensure consistency while parsing.

  3. Parsing Terms: A while loop runs to parse each term in the string. If the sign is '+', sign is set to 1, otherwise to -1. A nested while loop collects the characters that belong to the same term until it hits a '+' or '-' (or the end of the string).

  4. Process Each Term: Once a term is identified, the algorithm determines whether it contains an 'x'. Depending on this check, the term is processed as either a coefficient of x (adding or subtracting from x as controlled by the sign) or a constant (adding or subtracting from y). Importantly, if only x is present without a numeric coefficient, the coefficient is considered to be 1.

  5. Return Values: The function returns the net coefficients of x and the net constant y for the given side of the equation.

Main Function Logic

  1. Split Equation: The original equation string is split into two parts at the equals sign ('=') to get the left-hand side a and right-hand side b.

  2. Apply Inner Function: The function f() is called on both sides of the equation to obtain the respective sums of x coefficients and constants (x1, y1 for LHS and x2, y2 for RHS).

  3. Evaluate and Construct Solution:

  • If both sides of the equation have the same net coefficient of x (x1 == x2), it is either "Infinite solutions" (if the constants are the same) or "No solution" (if the constants differ).
  • If the net coefficients of x differ, we calculate the value of x by (y2 - y1) // (x1 - x2) to find the solution and construct the result string in the format "x=#value".

By using simple arithmetic operations and control flow, the solution effectively reduces the algebraic equation to its simplest form to find the solution for the variable x. This systematic approach allows the solution code to handle equations with varying coefficients and constant terms while determining the correct outcome among the three possible scenarios.

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

Which of the following is a good use case for backtracking?

Example Walkthrough

Let's use a small example to illustrate the solution approach: "3x+5=2x+10".

  1. Initialization: We shall initialize x and y to 0 for both sides of the equation before processing.

  2. Handling Signage: Since the equation has "+" and "-" symbols clearly defining each term, we don't have to prepend any additional signs.

  3. Split Equation: We split the equation at the '=' to get the left-hand side (LHS) "3x+5" and right-hand side (RHS) "2x+10".

  4. Apply Inner Function f(s) to LHS:

    • Parse the LHS "3x+5"
    • Identify and process terms "3x" and "+5"
    • For "3x", set x to +3 (since the sign is +)
    • For "+5", set y to +5
    • The LHS sums are x1=3 and y1=5

  5. Apply Inner Function f(s) to RHS:

    • Parse the RHS "2x+10"
    • Identify and process terms "2x" and "+10"
    • For "2x", set x to +2
    • For "+10", set y to +10
    • The RHS sums are x2=2 and y2=10

  6. Evaluate and Construct Solution:

    • Since x1=3 and x2=2 are not equal, we have one unique solution.
    • Calculate the value of x: (y2 - y1) / (x1 - x2) = (10 - 5) / (3 - 2) = 5 / 1 = 5
    • Construct the result string in the format "x=#value" which is "x=5" for this example.

Using this approach, we have determined that the variable x has the value of 5 in the equation "3x+5=2x+10". The consistent step-by-step method outlined in the solution approach allows us to parse the equation, identify and process terms, and evaluate the final solution with clarity.

Solution Implementation

1class Solution:
2    def solveEquation(self, equation: str) -> str:
3        # Helper function to process each side of the equation
4        def process_side(side):
5            coefficient_x = total_number = 0
6            if side[0] != '-':
7                side = '+' + side
8            idx, length = 0, len(side)
9            while idx < length:
10                sign = 1 if side[idx] == '+' else -1
11                idx += 1
12                j = idx
13                while j < length and side[j] not in '+-':
14                    j += 1
15                term = side[idx:j]
16                # If the term ends with 'x', it contributes to coefficient of x
17                if term[-1] == 'x':
18                    coefficient_x += sign * (int(term[:-1]) if len(term) > 1 else 1)
19                else:
20                    # Otherwise, it contributes to the total number
21                    total_number += sign * int(term)
22                idx = j
23            return coefficient_x, total_number
24
25        # Split the equation into left and right sides
26        left_side, right_side = equation.split('=')
27        # Process each side to get coefficients and numbers
28        coefficient_x_left, total_number_left = process_side(left_side)
29        coefficient_x_right, total_number_right = process_side(right_side)
30      
31        # Handling cases of infinite solutions or no solution
32        if coefficient_x_left == coefficient_x_right:
33            if total_number_left == total_number_right:
34                return 'Infinite solutions'
35            else:
36                return 'No solution'
37        # Calculating value of x
38        return f'x={(total_number_right - total_number_left) // (coefficient_x_left - coefficient_x_right)}'
39
1class Solution {
2    public String solveEquation(String equation) {
3        // Split the equation into two parts, before and after the '=' sign.
4        String[] parts = equation.split("=");
5        // The left part of the equation is processed to get coefficients of x and the constant term.
6        int[] leftCoefficients = parsePart(parts[0]);
7        // The right part of the equation is processed to get coefficients of x and the constant term.
8        int[] rightCoefficients = parsePart(parts[1]);
9      
10        // Assign the coefficients for easier readability.
11        int leftXCoefficient = leftCoefficients[0];
12        int leftConstant = leftCoefficients[1];
13        int rightXCoefficient = rightCoefficients[0];
14        int rightConstant = rightCoefficients[1];
15      
16        // Check if the coefficients of x are the same on both sides.
17        if (leftXCoefficient == rightXCoefficient) {
18            // If constants are also the same, it means there are infinite solutions.
19            // Otherwise, it means there is no solution.
20            return leftConstant == rightConstant ? "Infinite solutions" : "No solution";
21        }
22        // If the coefficients of x are different, solve for x.
23        return "x=" + (rightConstant - leftConstant) / (leftXCoefficient - rightXCoefficient);
24    }
25
26    // Helper method to process each part of the equation.
27    private int[] parsePart(String part) {
28        // Initial values for coefficients of x and constant.
29        int xCoefficient = 0;
30        int constant = 0;
31      
32        // Ensure we handle a leading '+' if it doesn't exist.
33        if (part.charAt(0) != '-') {
34            part = "+" + part;
35        }
36      
37        // Initialize index to traverse the string.
38        int index = 0;
39        // Length of the current part of the equation.
40        int length = part.length();
41        // Traverse part of the equation to calculate coefficients.
42        while (index < length) {
43            // Determine the sign of the current part (+1 for positive, -1 for negative).
44            int sign = part.charAt(index) == '+' ? 1 : -1;
45            index++;
46            // Remember where the number starts.
47            int numberStartIndex = index;
48            // Locate the end of the number or 'x'.
49            while (index < length && part.charAt(index) != '+' && part.charAt(index) != '-') {
50                index++;
51            }
52            // Extract the current value (either a coefficient or constant).
53            String value = part.substring(numberStartIndex, index);
54            // Check if the value corresponds to x or a constant.
55            if (part.charAt(index - 1) == 'x') {
56                // Parse the coefficient of 'x' and apply the sign.
57                xCoefficient += sign * (value.length() > 1 ? Integer.parseInt(value.substring(0, value.length() - 1)) : 1);
58            } else {
59                // Parse the constant and apply the sign.
60                constant += sign * Integer.parseInt(value);
61            }
62        }
63        // Return the coefficients as an array.
64        return new int[] {xCoefficient, constant};
65    }
66}
67
1#include <string>
2#include <iostream>
3
4// Function to solve a linear equation of the form "ax+b=cx+d"
5std::string solveEquation(std::string equation) {
6    // Split the equation into its left and right parts at the '=' sign
7    size_t equalPos = equation.find('=');
8    std::string leftSide = equation.substr(0, equalPos);
9    std::string rightSide = equation.substr(equalPos + 1);
10
11    // Helper function to parse an expression (either left or right part of the equation)
12    auto parseExpression = [](const std::string &expr) -> std::pair<int, int> {
13        int coefficientX = 0; // Holds the coefficient of 'x'
14        int constantTerm = 0; // Holds the constant term
15        int currentNumber = 0; // Holds the current parsed number
16        int sign = 1; // Holds the current sign (1 for positive, -1 for negative)
17        bool isVariable = false; // Flag to check if we're parsing a variable 'x'
18
19        // Iterate over each character in the expression
20        for (char ch : expr) {
21            if (ch == '+' || ch == '-') {
22                // On encountering a '+' or '-', update the coefficients and constants
23                if (isVariable) {
24                    coefficientX += currentNumber * sign;
25                } else {
26                    constantTerm += currentNumber * sign;
27                }
28                // Reset for the next term
29                isVariable = false;
30                currentNumber = 0;
31                sign = ch == '+' ? 1 : -1;
32            } else if (ch == 'x') {
33                isVariable = true;
34            } else if (isdigit(ch)) {
35                // Accumulate the number from the digits
36                currentNumber = currentNumber * 10 + (ch - '0');
37            }
38        }
39
40        // After the loop, need to update the coefficients and constants one last time
41        if (isVariable) {
42            coefficientX += (currentNumber == 0 ? 1 : currentNumber) * sign;
43        } else {
44            constantTerm += currentNumber * sign;
45        }
46
47        return {coefficientX, constantTerm};
48    };
49
50    // Parse both sides of the equation to get coefficients and constant terms
51    std::pair<int, int> leftExpr = parseExpression(leftSide);
52    std::pair<int, int> rightExpr = parseExpression(rightSide);
53
54    // If the coefficient of 'x' is the same on both sides, check for no solution or infinite solutions
55    if (leftExpr.first == rightExpr.first) {
56        if (leftExpr.second == rightExpr.second) {
57            return "Infinite solutions";
58        } else {
59            return "No solution";
60        }
61    }
62
63    // If there is a valid solution for 'x', calculate and return the value
64    int xValue = (rightExpr.second - leftExpr.second) / (leftExpr.first - rightExpr.first);
65    return "x=" + std::to_string(xValue);
66}
67
1function solveEquation(equation: string): string {
2    // Split the equation into its left and right parts
3    const [leftSide, rightSide] = equation.split('=');
4  
5    // Helper function to parse an expression (either left or right part of the equation)
6    const parseExpression = (expr: string): [number, number] => {
7        let coefficientX = 0; // holds the coefficient of x
8        let constantTerm = 0; // holds the constant term
9        let currentNumber = 0; // holds the current parsed number
10        let sign = 1; // holds the current sign (1 for positive, -1 for negative)
11        let isVariable = false; // flag to check if we're parsing a variable 'x'
12      
13        // Iterate over each character in the expression
14        for (const char of expr) {
15            if (char === '+' || char === '-') {
16                // On encountering a '+' or '-', update the coeffs and constants
17                if (isVariable) {
18                    coefficientX += currentNumber * sign;
19                } else {
20                    constantTerm += currentNumber * sign;
21                }
22                // Reset for the next term
23                isVariable = false;
24                currentNumber = 0;
25                sign = char === '+' ? 1 : -1;
26            } else if (char === 'x') {
27                isVariable = true;
28            } else {
29                // Accumulate the number from the digits
30                currentNumber = currentNumber * 10 + Number(char);
31            }
32        }
33      
34        // After the loop, need to update the coeffs and constants one last time
35        if (isVariable) {
36            coefficientX += (currentNumber || 1) * sign; // Assign 1 if no number before x
37        } else {
38            constantTerm += currentNumber * sign;
39        }
40      
41        return [coefficientX, constantTerm];
42    };
43  
44    // Parse both sides of the equation
45    const leftExpr = parseExpression(leftSide);
46    const rightExpr = parseExpression(rightSide);
47  
48    // If the coefficient of x is the same on both sides, check for no or infinite solutions
49    if (leftExpr[0] === rightExpr[0]) {
50        if (leftExpr[1] === rightExpr[1]) {
51            return 'Infinite solutions';
52        } else {
53            return 'No solution';
54        }
55    }
56
57    // If there is a valid solution for x, calculate and return the value
58    return `x=${(rightExpr[1] - leftExpr[1]) / (leftExpr[0] - rightExpr[0])}`;
59}
60
Not Sure What to Study? Take the 2-min Quiz：

Which type of traversal does breadth first search do?

Time and Space Complexity

The given Python code defines a function solveEquation which solves a linear equation in the form of a string and returns the result. The computational complexity analysis is as follows:

Time Complexity:

The function f(s) within the solveEquation function is responsible for evaluating each side of the equation. Let's call the length of the input equation n.

  1. The function iterates over each character of the input equation string at most once, which results in O(n) time complexity for the parsing steps.

  2. The operation split('='), which separates the equation into the left and right sides, executes in O(n) time.

  3. The function f(s) is called twice, once for each side of the equation. Each call iterates the string with length proportional to the length of that side – this remains within overall O(n) time.

  4. The operations to calculate the values of x and y are constant-time arithmetic operations, thus do not increase the complexity class.

  5. The final arithmetic operations to calculate the value of x are also constant-time operations.

Combining all these steps, the overall time complexity of the solveEquation function is O(n), where n is the length of the equation string.

Space Complexity:

  1. The space complexity is O(1) for the variables x, y, sign, v, x1, y1, x2, y2, a, and b as their space requirement does not scale with the size of the input.

  2. Temporary variables i, j, and s, when assigned the slices of the input string, also do not increase the space complexity as these are reference assignments to parts of the original string and don't require additional space proportional to the size of the input string.

  3. There is no additional data structure that grows with the input size. The space required is only for a fixed number of variables and their fixed-size contents.

  4. The auxiliary space used also does not depend on the input size, as it only involves a small number of fixed-size integer variables.

Considering all of the above points, the overall space complexity of the solveEquation function is O(1) – constant space complexity, as the space required does not scale with the size of the input.

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

Fast Track Your Learning with Our Quick Skills Quiz:

Is the following code DFS or BFS?

1void search(Node root) {
2  if (!root) return;
3  visit(root);
4  root.visited = true;
5  for (Node node in root.adjacent) {
6    if (!node.visited) {
7      search(node);
8    }
9  }
10}

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

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

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 algomonster s3 us east 2 amazonaws com recursion jpg You first

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.

←
↑TA 👨‍🏫