67. Add Binary

Posted on One min read

1. Description

Given two binary strings a and b, return their sum as a binary string.

2. Example

Example 1

Input: a = “11”, b = “1”
Output: “100”

Example 2

Input: a = “1010”, b = “1011”
Output: “10101”

3. Constraints

  • 1 <= a.length, b.length <= 10$^{4}$
  • a and b consist only of ‘0’ or ‘1’ characters.
  • Each string does not contain leading zeros except for the zero itself.

4. Solutions

Bit Manipulation

m = a.size(), n = b.size()
Time complexity: O(max(m, n))
Space complexity: O(1)

 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 {
public:
    string addBinary(const string &a, const string &b) {
        const int m = a.size(), n = b.size();
        string result;
        result.reserve(max(m, n) + 1);

        int carry = 0;
        for (int i = m - 1, j = n - 1; i >= 0 || j >= 0; --i, --j) {
            int sum = carry + (i >= 0 ? a[i] - '0' : 0) + (j >= 0 ? b[j] - '0' : 0);
            carry = sum / 2;
            result.push_back('0' + sum % 2);
        }

        if (carry == 1) {
            result.push_back('1');
        }

        reverse(result.begin(), result.end());

        return result;
    }
};
comments powered by Disqus