[LeetCode] 67. Add Binary

Posted on | In

Problem

Given two binary strings, return their sum (also a binary string).

The input strings are both non-empty and contains only characters 1 or 0.

Example 1:

1
2
Input: a = "11", b = "1"
Output: "100"

Example 2:

1
2
Input: a = "1010", b = "1011"
Output: "10101"

Explanation

  1. Similar to 2. Add Two Numbers. First, we need to create a stringbuilder res to hold the result. We need a pointer pointing at the end index of stringA, and another pointer pointing at the end index of stringB because we add these two numbers starting from the least significant digit.

  2. While either of the pointer is not negative, We can create a sum to hold the sum of two digit each time we add, and initialize the this sum equal to carry, where carry initialize to 0 before we start calculating.

  3. After adding two digits to the sum, now the result digit’s value will be sum % 2 and we added it to the stringbuilder, and carry will be sum / 2. Repeat this while loop.

  4. Outside of the while loop, if the carry is not zero, then we append it to the res, and we reverse the res and return its string representation.

Solution

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 addBinary(String a, String b) {
        int ptrA = a.length() - 1;
        int ptrB = b.length() - 1;
        StringBuilder sb = new StringBuilder();

        int carry = 0, sum = 0;
        while (ptrA >= 0 || ptrB >= 0) {
            sum = carry;
            if (ptrA >= 0) {
                sum += a.charAt(ptrA) - '0';
            }
            if (ptrB >= 0) {
                sum += b.charAt(ptrB) - '0';
            }
            sb.append(sum % 2);
            carry = sum / 2;
            ptrA -= 1;
            ptrB -= 1;
        }

        if (carry > 0) {
            sb.append(carry);
        }

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