Problem

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.

Examples

Example 1

1
2
3
4
5
6


    
    
    Input: equation = "x+5-3+x=6+x-2"
    Output: "x=2"

Example 2

1
2
3
4
5
6


    
    
    Input: equation = "x=x"
    Output: "Infinite solutions"

Example 3

1
2
3
4
5
6


    
    
    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.

Solution

Method 1 – Linear Scan and Coefficient Aggregation

Intuition

The key idea is to treat the equation as two sides separated by ‘=’, and aggregate the coefficients of ‘x’ and the constants on both sides. By moving all ‘x’ terms to one side and constants to the other, we can solve for ‘x’ directly. This works because the equation is always linear and only contains ‘+’, ‘-’, numbers, and ‘x’.

Approach

  1. Split the equation into left and right parts at ‘=’.
  2. For each side, scan the string and sum up:
    • The coefficients of ‘x’.
    • The constant terms.
  3. Move all ‘x’ terms to the left and constants to the right.
  4. If the coefficient of ‘x’ is 0:
    • If the constant is also 0, return “Infinite solutions”.
    • Otherwise, return “No solution”.
  5. Otherwise, return the integer solution for ‘x’.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
public:
    string solveEquation(string eq) {
        auto parse = [](const string& s) {
            int x = 0, c = 0, n = s.size(), sign = 1, i = 0;
            while (i < n) {
                if (s[i] == '+') { sign = 1; ++i; }
                else if (s[i] == '-') { sign = -1; ++i; }
                int j = i, num = 0, hasNum = false;
                while (j < n && isdigit(s[j])) { num = num * 10 + (s[j++] - '0'); hasNum = true; }
                if (j < n && s[j] == 'x') {
                    x += sign * (hasNum ? num : 1);
                    ++j;
                } else if (hasNum) {
                    c += sign * num;
                }
                i = j;
            }
            return make_pair(x, c);
        };
        int eqPos = eq.find('=');
        auto [lx, lc] = parse(eq.substr(0, eqPos));
        auto [rx, rc] = parse(eq.substr(eqPos + 1));
        int cx = lx - rx, cc = rc - lc;
        if (cx == 0) return cc == 0 ? "Infinite solutions" : "No solution";
        return "x=" + to_string(cc / cx);
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

func solveEquation(eq string) string {
    parse := func(s string) (int, int) {
        x, c, sign, n := 0, 0, 1, len(s)
        for i := 0; i < n; {
            if s[i] == '+' { sign = 1; i++ }
            if i < n && s[i] == '-' { sign = -1; i++ }
            num, hasNum := 0, false
            for i < n && s[i] >= '0' && s[i] <= '9' {
                num = num*10 + int(s[i]-'0')
                i++
                hasNum = true
            }
            if i < n && s[i] == 'x' {
                if hasNum { x += sign * num } else { x += sign }
                i++
            } else if hasNum {
                c += sign * num
            }
        }
        return x, c
    }
    eqPos := 0
    for i, ch := range eq { if ch == '=' { eqPos = i; break } }
    lx, lc := parse(eq[:eqPos])
    rx, rc := parse(eq[eqPos+1:])
    cx, cc := lx-rx, rc-lc
    if cx == 0 {
        if cc == 0 { return "Infinite solutions" }
        return "No solution"
    }
    return "x=" + strconv.Itoa(cc/cx)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
    public String solveEquation(String eq) {
        int[] l = parse(eq.substring(0, eq.indexOf('=')));
        int[] r = parse(eq.substring(eq.indexOf('=') + 1));
        int cx = l[0] - r[0], cc = r[1] - l[1];
        if (cx == 0) return cc == 0 ? "Infinite solutions" : "No solution";
        return "x=" + (cc / cx);
    }
    private int[] parse(String s) {
        int x = 0, c = 0, sign = 1, n = s.length(), i = 0;
        while (i < n) {
            if (s.charAt(i) == '+') { sign = 1; i++; }
            else if (s.charAt(i) == '-') { sign = -1; i++; }
            int num = 0, hasNum = 0;
            while (i < n && Character.isDigit(s.charAt(i))) {
                num = num * 10 + (s.charAt(i) - '0');
                i++; hasNum = 1;
            }
            if (i < n && s.charAt(i) == 'x') {
                x += sign * (hasNum == 1 ? num : 1);
                i++;
            } else if (hasNum == 1) {
                c += sign * num;
            }
        }
        return new int[]{x, c};
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
    fun solveEquation(eq: String): String {
        fun parse(s: String): Pair<Int, Int> {
            var x = 0; var c = 0; var sign = 1; var i = 0
            while (i < s.length) {
                if (s[i] == '+') { sign = 1; i++ }
                else if (s[i] == '-') { sign = -1; i++ }
                var num = 0; var hasNum = false
                while (i < s.length && s[i].isDigit()) {
                    num = num * 10 + (s[i] - '0'); i++; hasNum = true
                }
                if (i < s.length && s[i] == 'x') {
                    x += sign * if (hasNum) num else 1; i++
                } else if (hasNum) {
                    c += sign * num
                }
            }
            return x to c
        }
        val eqPos = eq.indexOf('=')
        val (lx, lc) = parse(eq.substring(0, eqPos))
        val (rx, rc) = parse(eq.substring(eqPos + 1))
        val cx = lx - rx; val cc = rc - lc
        return when {
            cx == 0 && cc == 0 -> "Infinite solutions"
            cx == 0 -> "No solution"
            else -> "x=${cc / cx}"
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution:
    def solveEquation(self, eq: str) -> str:
        def parse(s: str) -> tuple[int, int]:
            x = c = 0
            n, i, sign = len(s), 0, 1
            while i < n:
                if s[i] == '+': sign, i = 1, i+1
                elif s[i] == '-': sign, i = -1, i+1
                num, has_num = 0, False
                while i < n and s[i].isdigit():
                    num = num*10 + int(s[i]); i += 1; has_num = True
                if i < n and s[i] == 'x':
                    x += sign * (num if has_num else 1); i += 1
                elif has_num:
                    c += sign * num
            return x, c
        eq_pos = eq.index('=')
        lx, lc = parse(eq[:eq_pos])
        rx, rc = parse(eq[eq_pos+1:])
        cx, cc = lx - rx, rc - lc
        if cx == 0:
            return "Infinite solutions" if cc == 0 else "No solution"
        return f"x={cc//cx}"
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

impl Solution {
    pub fn solve_equation(eq: String) -> String {
        fn parse(s: &str) -> (i32, i32) {
            let (mut x, mut c, mut sign, mut i, n) = (0, 0, 1, 0, s.len());
            let s = s.as_bytes();
            while i < n {
                if s[i] == b'+' { sign = 1; i += 1; }
                else if s[i] == b'-' { sign = -1; i += 1; }
                let mut num = 0; let mut has_num = false;
                while i < n && s[i].is_ascii_digit() {
                    num = num * 10 + (s[i] - b'0') as i32; i += 1; has_num = true;
                }
                if i < n && s[i] == b'x' {
                    x += sign * if has_num { num } else { 1 }; i += 1;
                } else if has_num {
                    c += sign * num;
                }
            }
            (x, c)
        }
        let eq_pos = eq.find('=').unwrap();
        let (lx, lc) = parse(&eq[..eq_pos]);
        let (rx, rc) = parse(&eq[eq_pos+1..]);
        let (cx, cc) = (lx - rx, rc - lc);
        if cx == 0 {
            if cc == 0 { "Infinite solutions".to_string() } else { "No solution".to_string() }
        } else {
            format!("x={}", cc/cx)
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
    solveEquation(eq: string): string {
        function parse(s: string): [number, number] {
            let x = 0, c = 0, sign = 1, i = 0;
            while (i < s.length) {
                if (s[i] === '+') { sign = 1; i++; }
                else if (s[i] === '-') { sign = -1; i++; }
                let num = 0, hasNum = false;
                while (i < s.length && s[i] >= '0' && s[i] <= '9') {
                    num = num * 10 + Number(s[i]); i++; hasNum = true;
                }
                if (i < s.length && s[i] === 'x') {
                    x += sign * (hasNum ? num : 1); i++;
                } else if (hasNum) {
                    c += sign * num;
                }
            }
            return [x, c];
        }
        const eqPos = eq.indexOf('=');
        const [lx, lc] = parse(eq.slice(0, eqPos));
        const [rx, rc] = parse(eq.slice(eqPos + 1));
        const cx = lx - rx, cc = rc - lc;
        if (cx === 0) return cc === 0 ? "Infinite solutions" : "No solution";
        return `x=${Math.floor(cc / cx)}`;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the equation string. Each character is processed at most once during parsing.
  • 🧺 Space complexity: O(1), since only a constant number of variables are used for aggregation, regardless of input size.