algoadvance

Leetcode 640. Solve the Equation

Problem Statement

The problem is to solve a linear equation represented as a string equation. The equation contains one variable x and is in the format of ax + b = cx + d. Here a, b, c, and d are integers (they can be positive, negative or zero). The goal is to find the value of x.

When parsing the equation, note:

Output either the solution, “No solution” if the equation has no solution, or “Infinite solutions” if the equation has infinitely many solutions.

Clarifying Questions

  1. Input Format: Should the input be considered as always being in a linear form involving one variable x?
    • Yes, the input is guaranteed to be a valid linear equation involving one variable x.
  2. Spaces: Do we need to handle spaces in the equation?
    • Spaces are part of the input string and should be handled appropriately, although typical inputs may not contain spaces.
  3. Integer Values: Are we expecting integer coefficients and constants only?
    • Yes, the coefficients and constants will be integers.

Strategy

  1. Parse the Equation:
    • Split the equation into two parts around the = sign.
    • Parse each part to evaluate the coefficients of x and the constants.
  2. Evaluate Each Side Independently:
    • For each side of the equation, go through terms to identify and accumulate coefficients of x and constants.
  3. Combine Results:
    • After parsing, combine the results from both sides and solve the linear equation ax + b = 0 form.
  4. Determine Output:
    • If the coefficient of x equals zero:
      • If the constant term is also zero, output “Infinite solutions”.
      • Otherwise, output “No solution”.
    • Else compute the solution for x and output it in the required format.

Code Implementation

#include <iostream>
#include <sstream>
using namespace std;

pair<int, int> parseEquationSide(const string& side) {
    int coefficient = 0, constant = 0;
    int sign = 1; // for the leading sign
    int num = 0;
    bool numStarted = false;
    
    for (size_t i = 0; i < side.size(); ++i) {
        char c = side[i];
        
        if (isdigit(c)) {
            numStarted = true;
            num = num * 10 + (c - '0');
        } else if (c == 'x') {
            // When x is directly prefixed by a digit, complete the number read so far
            if (!numStarted) num = 1;
            coefficient += sign * num;
            numStarted = false;
            num = 0;
        } else if (c == '+' || c == '-') {
            // Complete the previous number if any
            if (numStarted) {
                constant += sign * num;
                numStarted = false;
                num = 0;
            }
            // Update the sign for the next number/x
            sign = (c == '-') ? -1 : 1;
        }
    }
    
    // If a number was in progress at the end
    if (numStarted) constant += sign * num;
    
    return {coefficient, constant};
}

string solveEquation(string equation) {
    size_t pos = equation.find('=');
    string left = equation.substr(0, pos);
    string right = equation.substr(pos + 1);
    
    // Parse both sides
    auto leftResult = parseEquationSide(left);
    auto rightResult = parseEquationSide(right);
    
    // Left: ax + b, Right: cx + d
    int coefficient = leftResult.first - rightResult.first;
    int constant = rightResult.second - leftResult.second;
    
    if (coefficient == 0) {
        if (constant == 0) return "Infinite solutions";
        else return "No solution";
    }
    
    int x = constant / coefficient;
    return "x=" + to_string(x);
}

int main() {
    string equation = "2x+3x-6x=x+2";
    cout << solveEquation(equation) << endl;
    return 0;
}

Time Complexity

The time complexity for parsing and solving the equation is O(n), where n is the length of the input string. The operations include parsing the string and performing constant-time arithmetic, both of which are linear concerning the input string length.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI