algoadvance

Leetcode 640. Solve the Equation

Problem Statement

You are given a string representing an equation with variables. The task is to solve the equation and return the value of the variable “x”. The equation consists of integers, variables, and operators (‘+’, ‘-‘, ‘=’) and should be balanced around the ‘=’ sign. Return the equation in this format: “x=#value”. If the equation has no solution, return “No solution”. If there are infinite solutions, return “Infinite solutions”.

Example:

Input: "x+5-3+x=6+x-2"
Output: "x=2"

Input: "x=x"
Output: "Infinite solutions"

Input: "2x=x"
Output: "x=0"

Input: "2x+3x-6x=x+2"
Output: "x=-1"

Input: "x=x+2"
Output: "No solution"

Clarifying Questions

  1. Can the input be empty or null?
    • Assumption: No, the input will always be a valid non-empty string.
  2. Will the input always contain ‘x’ and ‘=’?
    • Assumption: Yes, the input will contain at least one ‘x’ and both sides of the ‘=’.
  3. Can we expect the input format to be valid?
    • Assumption: Yes, the input will always be in a valid equation format.

Strategy

  1. Parse the Equation:
    • Split the input equation into two parts around the ‘=’ character.
  2. Normalize Each Side:
    • For each side, collect coefficients for ‘x’ and constants.
    • Use appropriate sign (+/-) for each component.
  3. Combine Like Terms:
    • Sum up coefficients for ‘x’ and constants separately for both left and right sides.
  4. Solve the Simplified Equation:
    • Isolate ‘x’ and solve for it.
    • Handle special cases for no solution or infinite solutions.

Code

public class SolveEquation {
    public String solveEquation(String equation) {
        String[] sides = equation.split("=");
        int[] left = evaluateExpression(sides[0]);
        int[] right = evaluateExpression(sides[1]);
        
        int coeffX = left[0] - right[0];
        int constant = right[1] - left[1];
        
        if (coeffX == 0) {
            if (constant == 0) {
                return "Infinite solutions";
            } else {
                return "No solution";
            }
        }
        
        int xValue = constant / coeffX;
        return "x=" + xValue;
    }
    
    private int[] evaluateExpression(String expr) {
        int coeffX = 0;
        int constant = 0;
        int n = expr.length();
        int sign = 1;
        int i = 0;
        
        while (i < n) {
            if (expr.charAt(i) == '+') {
                sign = 1;
                i++;
            } else if (expr.charAt(i) == '-') {
                sign = -1;
                i++;
            } else {
                int coef = 0;
                boolean isDigit = false;
                while (i < n && Character.isDigit(expr.charAt(i))) {
                    coef = coef * 10 + (expr.charAt(i) - '0');
                    i++;
                    isDigit = true;
                }
                if (i < n && expr.charAt(i) == 'x') {
                    if (coef == 0 && !isDigit) coef = 1;
                    coeffX += coef * sign;
                    i++;
                } else {
                    constant += coef * sign;
                }
            }
        }
        
        return new int[]{coeffX, constant};
    }
    
    public static void main(String[] args) {
        SolveEquation solver = new SolveEquation();
        System.out.println(solver.solveEquation("x+5-3+x=6+x-2")); // "x=2"
        System.out.println(solver.solveEquation("x=x")); // "Infinite solutions"
        System.out.println(solver.solveEquation("2x=x")); // "x=0"
        System.out.println(solver.solveEquation("2x+3x-6x=x+2")); // "x=-1"
        System.out.println(solver.solveEquation("x=x+2")); // "No solution"
    }
}

Time Complexity

  1. Parsing the Equation: O(n), where n is the length of the equation string.
  2. Evaluating Each Side: O(n) for each side.
  3. Therefore, the overall time complexity is O(n).

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