</>Ali · LeetCode
#0067·EasyMath

Add Binary

LeetCode #67 · Easy · Math · C++ solution with worked-out approach and complexity analysis.

View on LeetCodeSource on GitHub

Approach

Simulate binary addition with carry

Strategy

  1. 1Start from the rightmost bits of both strings
  2. 2Add corresponding bits plus any carry from previous position
  3. 3Calculate the result bit (sum % 2) and new carry (sum / 2)
  4. 4Insert the result bit at the beginning of the result string
  5. 5Continue until both strings are exhausted
  6. 6If there's a remaining carry, add it to the front
Time
O(max(n, m))
n and m are lengths of a and b
Space
O(max(n, m))
the result string
Problem description(from LeetCode)

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

Examples

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

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.

C++ Solution

solution.cpp
class Solution {
public:
string addBinary(string a, string b) {
    int carry = 0, n = a.size() - 1, m = b.size() - 1;
    string res = "";
    while (n >= 0 || m >= 0) {
      int bit1 = n < 0 ? 0 : (a[n] - '0');
      int bit2 = m < 0 ? 0 : (b[m] - '0');
      int sum = bit1 + bit2 + carry;
      int bit = sum % 2;
      carry = sum / 2;
      res.insert(res.begin(), bit + '0');
      n--;
      m--;
    }

    if (carry > 0) {
      res.insert(res.begin(), carry + '0');
    }

    return res;
  }
};

More Math problems