Overflow in intermediate arithmetic
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.
Move from brute-force thinking to an efficient approach using math strategy.
Solve a given equation and return the value of 'x' in the form of a string "x=#value". The equation contains only '+', '-' operation, the variable 'x' and its coefficient. You should return "No solution" if there is no solution for the equation, or "Infinite solutions" if there are infinite solutions for the equation.
If there is exactly one solution for the equation, we ensure that the value of 'x' is an integer.
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 <= 1000equation has exactly one '='.equation consists of integers with an absolute value in the range [0, 100] without any leading zeros, and the variable 'x'.Problem summary: Solve a given equation and return the value of 'x' in the form of a string "x=#value". The equation contains only '+', '-' operation, the variable 'x' and its coefficient. You should return "No solution" if there is no solution for the equation, or "Infinite solutions" if there are infinite solutions for the equation. If there is exactly one solution for the equation, we ensure that the value of 'x' is an integer.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Math
"x+5-3+x=6+x-2"
"x=x"
"2x=x"
fraction-addition-and-subtraction)minimize-result-by-adding-parentheses-to-expression)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #640: Solve the Equation
class Solution {
public String solveEquation(String equation) {
String[] es = equation.split("=");
int[] a = f(es[0]), b = f(es[1]);
int x1 = a[0], y1 = a[1];
int x2 = b[0], y2 = b[1];
if (x1 == x2) {
return y1 == y2 ? "Infinite solutions" : "No solution";
}
return "x=" + (y2 - y1) / (x1 - x2);
}
private int[] f(String s) {
int x = 0, y = 0;
if (s.charAt(0) != '-') {
s = "+" + s;
}
int i = 0, n = s.length();
while (i < n) {
int sign = s.charAt(i) == '+' ? 1 : -1;
++i;
int j = i;
while (j < n && s.charAt(j) != '+' && s.charAt(j) != '-') {
++j;
}
String v = s.substring(i, j);
if (s.charAt(j - 1) == 'x') {
x += sign * (v.length() > 1 ? Integer.parseInt(v.substring(0, v.length() - 1)) : 1);
} else {
y += sign * Integer.parseInt(v);
}
i = j;
}
return new int[] {x, y};
}
}
// Accepted solution for LeetCode #640: Solve the Equation
func solveEquation(equation string) string {
f := func(s string) []int {
x, y := 0, 0
if s[0] != '-' {
s = "+" + s
}
i, n := 0, len(s)
for i < n {
sign := 1
if s[i] == '-' {
sign = -1
}
i++
j := i
for j < n && s[j] != '+' && s[j] != '-' {
j++
}
v := s[i:j]
if s[j-1] == 'x' {
a := 1
if len(v) > 1 {
a, _ = strconv.Atoi(v[:len(v)-1])
}
x += sign * a
} else {
a, _ := strconv.Atoi(v)
y += sign * a
}
i = j
}
return []int{x, y}
}
es := strings.Split(equation, "=")
a, b := f(es[0]), f(es[1])
x1, y1 := a[0], a[1]
x2, y2 := b[0], b[1]
if x1 == x2 {
if y1 == y2 {
return "Infinite solutions"
} else {
return "No solution"
}
}
return fmt.Sprintf("x=%d", (y2-y1)/(x1-x2))
}
# Accepted solution for LeetCode #640: Solve the Equation
class Solution:
def solveEquation(self, equation: str) -> str:
def f(s):
x = y = 0
if s[0] != '-':
s = '+' + s
i, n = 0, len(s)
while i < n:
sign = 1 if s[i] == '+' else -1
i += 1
j = i
while j < n and s[j] not in '+-':
j += 1
v = s[i:j]
if v[-1] == 'x':
x += sign * (int(v[:-1]) if len(v) > 1 else 1)
else:
y += sign * int(v)
i = j
return x, y
a, b = equation.split('=')
x1, y1 = f(a)
x2, y2 = f(b)
if x1 == x2:
return 'Infinite solutions' if y1 == y2 else 'No solution'
return f'x={(y2 - y1) // (x1 - x2)}'
// Accepted solution for LeetCode #640: Solve the Equation
struct Solution;
impl Solution {
fn solve_equation(equation: String) -> String {
let mut it = equation.split('=');
let left = it.next().unwrap();
let right = it.next().unwrap();
let (a, b) = Self::parse(left);
let (c, d) = Self::parse(right);
if a == c {
if b == d {
"Infinite solutions".to_string()
} else {
"No solution".to_string()
}
} else {
format!("x={}", (d - b) / (a - c))
}
}
fn parse(s: &str) -> (i32, i32) {
let mut sign = 1;
let mut x = false;
let mut val = None;
let mut a = 0;
let mut b = 0;
for c in s.chars() {
match c {
'x' => {
if val.is_none() {
val = Some(1);
}
x = true;
}
'+' => {
if let Some(v) = val {
if x {
a += sign * v;
} else {
b += sign * v;
}
}
val = None;
x = false;
sign = 1;
}
'-' => {
if let Some(v) = val {
if x {
a += sign * v;
} else {
b += sign * v;
}
}
val = None;
x = false;
sign = -1;
}
_ => {
val = if let Some(mut v) = val {
v *= 10;
v += (c as u8 - b'0') as i32;
Some(v)
} else {
Some((c as u8 - b'0') as i32)
};
}
}
}
if x {
if val.is_none() {
val = Some(1);
}
a += sign * val.unwrap();
} else {
b += sign * val.unwrap();
}
(a, b)
}
}
#[test]
fn test() {
let equation = "x+5-3+x=6+x-2".to_string();
let res = "x=2".to_string();
assert_eq!(Solution::solve_equation(equation), res);
let equation = "x=x".to_string();
let res = "Infinite solutions".to_string();
assert_eq!(Solution::solve_equation(equation), res);
let equation = "2x=x".to_string();
let res = "x=0".to_string();
assert_eq!(Solution::solve_equation(equation), res);
let equation = "2x+3x-6x=x+2".to_string();
let res = "x=-1".to_string();
assert_eq!(Solution::solve_equation(equation), res);
let equation = "x=x+2".to_string();
let res = "No solution".to_string();
assert_eq!(Solution::solve_equation(equation), res);
let equation = "0x=0".to_string();
let res = "Infinite solutions".to_string();
assert_eq!(Solution::solve_equation(equation), res);
let equation = "-x=-1".to_string();
let res = "x=1".to_string();
assert_eq!(Solution::solve_equation(equation), res);
}
// Accepted solution for LeetCode #640: Solve the Equation
function solveEquation(equation: string): string {
const [left, right] = equation.split('=');
const createExpr = (s: string) => {
let x = 0;
let n = 0;
let i = 0;
let sym = 1;
let cur = 0;
let isX = false;
for (const c of s) {
if (c === '+' || c === '-') {
if (isX) {
if (i === 0 && cur === 0) {
cur = 1;
}
x += cur * sym;
} else {
n += cur * sym;
}
isX = false;
cur = 0;
i = 0;
if (c === '+') {
sym = 1;
} else {
sym = -1;
}
} else if (c === 'x') {
isX = true;
} else {
i++;
cur *= 10;
cur += Number(c);
}
}
if (isX) {
if (i === 0 && cur === 0) {
cur = 1;
}
x += cur * sym;
} else {
n += cur * sym;
}
return [x, n];
};
const lExpr = createExpr(left);
const rExpr = createExpr(right);
if (lExpr[0] === rExpr[0]) {
if (lExpr[1] !== rExpr[1]) {
return 'No solution';
}
return 'Infinite solutions';
}
return `x=${(lExpr[1] - rExpr[1]) / (rExpr[0] - lExpr[0])}`;
}
Use this to step through a reusable interview workflow for this problem.
Simulate the process step by step — multiply n times, check each number up to n, or iterate through all possibilities. Each step is O(1), but doing it n times gives O(n). No extra space needed since we just track running state.
Math problems often have a closed-form or O(log n) solution hidden behind an O(n) simulation. Modular arithmetic, fast exponentiation (repeated squaring), GCD (Euclidean algorithm), and number theory properties can dramatically reduce complexity.
Review these before coding to avoid predictable interview regressions.
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.