Solve the Equation

Problem Statement

In this task, you are given an equation involving a variable 'x', integers, and the operations '+' and '-'. Your goal is to solve this equation for 'x' and provide the solution in the format "x=#value", where "#value" represents the integer solution. If no solution exists under normal algebraic rules, return "No solution". In cases where any value of 'x' satisfies the equation (indicating infinite solutions), return "Infinite solutions". The provided equation will contain only one equals sign, setting up an equality between two expressions, and is expected to be well-formed and valid based on given conditions.

Examples

Example 1

Input:

equation = "x+5-3+x=6+x-2"

Output:

"x=2"

Example 2

Input:

equation = "x=x"

Output:

"Infinite solutions"

Example 3

Input:

equation = "2x=x"

Output:

"x=0"

Constraints

• 3 <= equation.length <= 1000
• equation has exactly one '='.
• equation consists of integers with an absolute value in the range [0, 100] without any leading zeros, and the variable 'x'.
• The input is generated that if there is a single solution, it will be an integer.

Approach and Intuition

To approach the problem of solving for 'x' in a given linear equation:

1. Initialize Counters: Start by initializing two variables, one for storing the cumulative coefficient of 'x' across the entire equation (total_x), and one for the constant terms (total_const).

2. Parse the Equation: Split the equation at the equals '=' sign to separate the left-hand side (LHS) and right-hand side (RHS).

3. Process Each Side: For both LHS and RHS:

   • Break down the side into individual terms (separated by '+' or '-').
   • Each term is either a constant or a multiple of 'x' (e.g., '3x', '-x', '+5', etc.).
   • Update the total_x and total_const based on whether the term includes 'x' or is just a numeric constant.

4. Balance the Equation: After distributing and aggregating coefficients and constants from both sides:

   • The coefficient of 'x' will be the difference between the coefficients of 'x' on the LHS and RHS.
   • The constants transferred from one side of the equation to the other will adjust the total_constant value.

5. Check for Infinite or No Solution Cases:

   • If the coefficient of 'x' after combining both sides results to zero (all 'x' terms cancel out):
     • If the resultant total_constant is also zero, the equation has infinite solutions.
     • If the resultant total_constant is non-zero, no real value of 'x' would satisfy the equation.

6. Calculate and Return Solution:

   • If there's a non-zero coefficient for 'x', the solution for 'x' can be found by dividing the (negative of) total_constant with the coefficient of 'x'.
   • Formulate the solution in the required format, ensuring that the solution is an integer as stated.

By following these steps, one can programmatically simulate the balancing of an equation around 'x', effectively solving for it or determining the nature of the solution.

Solutions

public class EquationSolver {
    public String extractCoefficient(String term) {
        if (term.length() > 1 && term.charAt(term.length() - 2) >= '0' && term.charAt(term.length() - 2) <= '9')
            return term.replace("x", "");
        return term.replace("x", "1");
    }
    public String calculateSolution(String equation) {
        String[] parts = equation.split("=");
        int leftSum = 0, rightSum = 0;
        for (String part: parts[0].split("(?=\\+)|(?=-)")) {
            if (part.contains("x")) {
                leftSum += Integer.parseInt(extractCoefficient(part));
            } else {
                rightSum -= Integer.parseInt(part);
            }
        }
        for (String part: parts[1].split("(?=\\+)|(?=-)")) {
            if (part.contains("x"))
                leftSum -= Integer.parseInt(extractCoefficient(part));
            else
                rightSum += Integer.parseInt(part);
        }
        if (leftSum == 0) {
            if (rightSum == 0)
                return "Infinite solutions";
            else
                return "No solution";
        } else
            return "x=" + rightSum / leftSum;
    }
}