640. Solve the Equation
Model: qwen3.5:9b
Topics: Math
FAANG asked: 1
Acceptance rate: 42.8%
Problem Breakdown
We are given a string representing a linear equation involving a single variable x and integer constants. The goal is to solve for x.
Inputs: A string containing +, -, x, digits, and exactly one = sign.
Outputs: A string indicating the solution (“x=#value”), “No solution”, or “Infinite solutions”.
Implicit Constraints & Edge Cases:
- Implicit Coefficients: Terms like
ximply a coefficient of1, while-ximplies-1. - Implicit Constants: A term like
5is a constant, not anxterm. - No Spaces: The input string typically does not contain spaces (though handling them is trivial).
- Integer Solutions: If a unique solution exists, the problem guarantees
xis an integer. - Overflow: Python handles large integers automatically, so standard overflow checks aren’t needed for logic, but we must ensure we don’t divide by zero.
Intuition
A brute-force approach would be to iterate through possible integer values of x, substitute them into the equation, and check if LHS equals RHS. However, since the range of integers is infinite (or at least very large), this is or impractical.
The key insight is that this is a linear equation of the form . We can treat the left-hand side (LHS) and right-hand side (RHS) independently.
- Parse the LHS to find the total coefficient of
x() and the sum of constants (). - Parse the RHS to find the total coefficient of
x() and the sum of constants (). - Rearrange the equation: .
- Let and . The equation simplifies to .
From here, we can determine the solution state based on :
- If and , every value of
xworks “Infinite solutions”. - If and , no value satisfies the equation “No solution”.
- If , there is exactly one solution .
Approach
- Split the Equation: Use
split('=')to separate the string into left and right parts. - Parse Function: Create a helper function (or logic) that takes a side of the equation and returns
(x_coefficient, constant_sum).- Iterate through characters maintaining a
current_sign(+1 or -1). - Accumulate digits into a
current_number. - If ‘x’ is encountered: add
sign * current_number(defaultingcurrent_numberto 1 if no digit was seen) to the x coefficient. Resetcurrent_number. - If ’+’ or ’-’ is encountered: update
current_sign. - At the end of the string, if a
current_numberexists, add it to the constant sum.
- Iterate through characters maintaining a
- Combine Results: Subtract RHS coefficients from LHS coefficients to move all terms to one side.
- Determine Output: Apply the logic derived in the Intuition section to return the correct string.
Complexity Analysis
- Time Complexity: , where is the length of the input string. We traverse the string once to parse coefficients and constants.
- Space Complexity: . We use a fixed amount of extra space for variables (coefficients, signs), regardless of input size.
Solution
def solveEquation(equation: str) -> str:
# Split equation into left and right sides
left, right = equation.split('=')
def parse_side(side):
x_coeff = 0
const_sum = 0
current_num = 0
sign = 1
for char in side:
if char.isdigit():
current_num = (current_num * 10) + int(char)
elif char == 'x':
# If no number was accumulated, coefficient is 1
coeff = current_num if current_num else 1
x_coeff += sign * coeff
current_num = 0
elif char == '+':
sign = 1
elif char == '-':
sign = -1
# Handle the last constant term if it exists (e.g., "x+5")
if current_num > 0:
const_sum += sign * current_num
return x_coeff, const_sum
x_l, c_l = parse_side(left)
x_r, c_r = parse_side(right)
# Move all x terms to left and constants to right: (x_l - x_r)x = c_r - c_l
total_x = x_l - x_r
total_const = c_r - c_l
if total_x == 0:
if total_const == 0:
return "Infinite solutions"
else:
return "No solution"
else:
# Problem guarantees integer solution for unique case
return f"x={total_const // total_x}"
Edge Cases Handled
- Implicit Coefficients: Logic handles
x(coeff 1) and-x(coeff -1) by checking ifcurrent_numis zero before multiplying. - Negative Signs: The
signvariable tracks the operator preceding a number orx, correctly handling cases like-2x+3. - No Solution / Infinite Solutions: Explicitly checks if
total_xis zero to distinguish between identity () and contradiction (). - Trailing Constants: The final check
if current_num > 0ensures constants at the end of a side (e.g., in “x+5”) are added to the sum.