Solve the Equation

• Split the input equation string at the '=' character to get the left-hand side (LHS) and right-hand side (RHS).
• Define a helper function, evaluate(expression), that takes a string expression and returns a pair of integers: [total_x_coefficient, total_constant_sum].
• Inside evaluate, use a regular expression or string splitting to break the expression into individual terms. A good method is to split the string using a positive lookahead (?=[+-]), which splits at + or - but keeps them as part of the following term. This results in an array of terms like ["x", "+5", "-3", "+x"].
• Iterate through the array of terms. For each term:
  • If it contains 'x', parse its coefficient. Note that "x" implies a coefficient of +1, and "-x" implies -1. Add this coefficient to the total_x_coefficient.
  • If it does not contain 'x', it's a constant. Parse it as an integer and add it to the total_constant_sum.
• Call the evaluate function on both the LHS and RHS strings.
• Let the results be [lhs_x, lhs_const] and [rhs_x, rhs_const].
• Rearrange the equation to the form Ax = B. The final coefficient of x is x_coeff = lhs_x - rhs_x, and the final constant value is const_val = rhs_const - lhs_const.
• Analyze the results:
  • If x_coeff is 0 and const_val is 0, the equation is 0 = 0, which means there are infinite solutions.
  • If x_coeff is 0 and const_val is not 0, the equation is 0 = non-zero, which is a contradiction, meaning no solution.
  • If x_coeff is not 0, there is a unique solution x = const_val / x_coeff.

The core idea is to parse each side of the equation to find the sum of x-coefficients and the sum of constants. We can achieve this by splitting the expression string into terms.

• Algorithm

• Split the input equation string at the '=' character to get the left-hand side (LHS) and right-hand side (RHS).

• Define a helper function, evaluate(expression), that takes a string expression and returns a pair of integers: [total_x_coefficient, total_constant_sum].

• Inside evaluate, use a regular expression or string splitting to break the expression into individual terms. A good method is to split the string using a positive lookahead (?=[+-]), which splits at + or - but keeps them as part of the following term. This results in an array of terms like ["x", "+5", "-3", "+x"].

• Iterate through the array of terms. For each term:

  • If it contains 'x', parse its coefficient. Note that "x" implies a coefficient of +1, and "-x" implies -1. Add this coefficient to the total_x_coefficient.
  • If it does not contain 'x', it's a constant. Parse it as an integer and add it to the total_constant_sum.

• Call the evaluate function on both the LHS and RHS strings.

• Let the results be [lhs_x, lhs_const] and [rhs_x, rhs_const].

• Rearrange the equation to the form Ax = B. The final coefficient of x is x_coeff = lhs_x - rhs_x, and the final constant value is const_val = rhs_const - lhs_const.

• Analyze the results:

  • If x_coeff is 0 and const_val is 0, the equation is 0 = 0, which means there are infinite solutions.
  • If x_coeff is 0 and const_val is not 0, the equation is 0 = non-zero, which is a contradiction, meaning no solution.
  • If x_coeff is not 0, there is a unique solution x = const_val / x_coeff.

• Code Snippet

1class Solution {2    public String solveEquation(String equation) {3        String[] parts = equation.split("=");4        int[] left = evaluate(parts[0]);5        int[] right = evaluate(parts[1]);6 7        int xCoeff = left[0] - right[0];8        int constVal = right[1] - left[1];9 10        if (xCoeff == 0) {11            if (constVal == 0) {12                return "Infinite solutions";13            } else {14                return "No solution";15            }16        } else {17            return "x=" + (constVal / xCoeff);18        }19    }20 21    private int[] evaluate(String expr) {22        int xCoeff = 0;23        int constSum = 0;24        String[] terms = expr.split("(?=[+-])");25        for (String term : terms) {26            if (term.equals("+") || term.equals("-")) continue;27            if (term.contains("x")) {28                String coeffPart = term.substring(0, term.length() - 1);29                if (coeffPart.isEmpty() || coeffPart.equals("+")) {30                    xCoeff++;31                } else if (coeffPart.equals("-")) {32                    xCoeff--;33                } else {34                    xCoeff += Integer.parseInt(coeffPart);35                }36            } else {37                constSum += Integer.parseInt(term);38            }39        }40        return new int[]{xCoeff, constSum};41    }42}

• Split the equation at the '=' to get LHS and RHS strings.
• Define a helper function evaluate(expression) that parses the expression in a single pass without creating intermediate collections.
• Inside evaluate, initialize variables: x_coeff = 0, const_sum = 0, sign = 1 (for the current term's sign), and current_num = 0 (for the number being parsed).
• Iterate through the expression string character by character from left to right.
• At each character:
  • If it's a digit, update current_num by appending the digit's value (e.g., current_num = current_num * 10 + digit).
  • If it's an 'x', this marks an x-term. The coefficient is the current_num parsed so far (or 1 if no number was parsed, e.g., for "+x"). Add sign * coefficient to x_coeff. Reset current_num for the next term.
  • If it's a '+' or '-', this signifies the end of the previous term (which must be a constant). Add sign * current_num to const_sum. Then, reset current_num and update the sign for the upcoming term.
• After the loop finishes, the last parsed number needs to be added to the const_sum.
• Call evaluate for both LHS and RHS.
• Combine the results and determine the solution using the same logic as the first approach.

Instead of splitting the string into an array of terms, we can process it character by character, which is more efficient in terms of memory.

• Algorithm

• Split the equation at the '=' to get LHS and RHS strings.

• Define a helper function evaluate(expression) that parses the expression in a single pass without creating intermediate collections.

• Inside evaluate, initialize variables: x_coeff = 0, const_sum = 0, sign = 1 (for the current term's sign), and current_num = 0 (for the number being parsed).

• Iterate through the expression string character by character from left to right.

• At each character:

  • If it's a digit, update current_num by appending the digit's value (e.g., current_num = current_num * 10 + digit).
  • If it's an 'x', this marks an x-term. The coefficient is the current_num parsed so far (or 1 if no number was parsed, e.g., for "+x"). Add sign * coefficient to x_coeff. Reset current_num for the next term.
  • If it's a '+' or '-', this signifies the end of the previous term (which must be a constant). Add sign * current_num to const_sum. Then, reset current_num and update the sign for the upcoming term.

• After the loop finishes, the last parsed number needs to be added to the const_sum.

• Call evaluate for both LHS and RHS.

• Combine the results and determine the solution using the same logic as the first approach.

• Code Snippet

1class Solution {2    public String solveEquation(String equation) {3        String[] parts = equation.split("=");4        int[] left = evaluate(parts[0]);5        int[] right = evaluate(parts[1]);6 7        int xCoeff = left[0] - right[0];8        int constVal = right[1] - left[1];9 10        if (xCoeff == 0) {11            return constVal == 0 ? "Infinite solutions" : "No solution";12        } else {13            return "x=" + (constVal / xCoeff);14        }15    }16 17    private int[] evaluate(String expr) {18        int xCoeff = 0;19        int constSum = 0;20        int sign = 1;21        int currentNum = 0;22        boolean hasNum = false;23 24        for (int i = 0; i < expr.length(); i++) {25            char c = expr.charAt(i);26            if (Character.isDigit(c)) {27                currentNum = currentNum * 10 + (c - '0');28                hasNum = true;29            } else if (c == 'x') {30                xCoeff += sign * (hasNum ? currentNum : 1);31                currentNum = 0;32                hasNum = false;33            } else { // c is '+' or '-'34                constSum += sign * currentNum;35                sign = (c == '+') ? 1 : -1;36                currentNum = 0;37                hasNum = false;38            }39        }40        // Add the last number if it exists41        constSum += sign * currentNum;42        43        return new int[]{xCoeff, constSum};44    }45}