67. Add Binary

LeetCode

Add and Carry

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
33
34
35
36
37
38
39
40
class Solution {
    public String addBinary(String a, String b) {
        int n = a.length();
        int m = b.length();

        StringBuilder sb = new StringBuilder();
        int max = Math.max(n, m);
        int carry = 0;
        for (int i = 0; i < max; i++) {
            int curA = 0;
            int curB = 0;
            if (n - i - 1 >= 0) {
                curA = a.charAt(n - i - 1) - '0';
            } else {
                curA = 0;
            }

            if (m - i - 1 >= 0) {
                curB = b.charAt(m - i - 1) - '0';
            } else {
                curB = 0;
            }

            if ((curA + curB + carry) < 2) {
                sb.insert(0, Integer.toString(curA + curB + carry));
                carry = 0;
            } else {
                sb.insert(0, Integer.toString((curA + curB + carry) % 2));
                carry = 1;
            }

        }

        if (carry == 1) {
            sb.insert(0, "1");
        }

        return sb.toString();
    }
}

Remarks:

  1. TC: $O(n^2)$ (sb.insert() moves all chars each time), SC: $O(n)$.
  2. if-else statements might be combined and simplified to:
    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
    class Solution {
        public String addBinary(String a, String b) {
            int n = a.length();
            int m = b.length();

            StringBuilder sb = new StringBuilder();
            int max = Math.max(n, m);
            int carry = 0;

            for (int i = 0; i < max; i++) {
                int curA = (n - i - 1 >= 0) ? a.charAt(n - i - 1) - '0' : 0;
                int curB = (m - i - 1 >= 0) ? b.charAt(m - i - 1) - '0' : 0;

                int sum = curA + curB + carry;
                sb.insert(0, sum % 2);
                carry = sum / 2;
            }

            if (carry == 1) {
                sb.insert(0, "1");
            }

            return sb.toString();
        }
    }
  3. If replace sb.insert(0, ...) by sb.append(...) + sb.reverse(), we can save more time, as below.

StringBuilder append + reverse

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public String addBinary(String a, String b) {
        int n = a.length();
        int m = b.length();

        StringBuilder sb = new StringBuilder();
        int carry = 0;
        int i = n - 1, j = m - 1;

        while (i >= 0 || j >= 0 || carry == 1) {
            int curA = (i >= 0) ? a.charAt(i--) - '0' : 0;
            int curB = (j >= 0) ? b.charAt(j--) - '0' : 0;

            int sum = curA + curB + carry;
            sb.append(sum % 2);
            carry = sum / 2;
        }

        return sb.reverse().toString();
    }
}

Remarks:

  1. TC: $O(n)$, SC: $O(n)$.