Description
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'.- The input is generated that if there is a single solution, it will be an integer.
Solutions
Solution 1: Mathematics
We split the equation by the equal sign "=" into left and right expressions, and compute the coefficient of "x" (denoted x_i) and the constant value (denoted y_i) for each side.
The equation is then transformed into: x_1 × x + y_1 = x_2 × x + y_2.
- When x_1 = x_2: if y_1 ≠ y_2, there is no solution; if y_1 = y_2, there are infinite solutions.
- When x_1 ≠ x_2: there is a unique solution x = y_2 - y_1⁄x_1 - x_2.
Similar problems:
PythonJavaGoTypeScript
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)}'(code-box)
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};
}
}(code-box)
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))
}(code-box)
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])}`;
}(code-box)
