67

67. Add Binary (Easy)

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

 

Example 1:

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

Example 2:

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

 

Constraints:

• 1 <= a.length, b.length <= 104
• a and b consist only of '0' or '1' characters.
• Each string does not contain leading zeros except for the zero itself.

Companies:
Facebook, Google, Adobe, Samsung, Apple, ByteDance

Related Topics:
Math, String, Bit Manipulation, Simulation

Similar Questions:

• Add Two Numbers (Medium)
• Multiply Strings (Medium)
• Plus One (Easy)
• Add to Array-Form of Integer (Easy)

Solution 1.

// OJ: https://leetcode.com/problems/add-binary/
// Author: github.com/lzl124631x
// Time: O(A+B)
// Space: O(1)
class Solution {
public:
    string addBinary(string a, string b) {
        int i = a.size() - 1, j = b.size() - 1, carry = 0;
        string ans;
        while (i >= 0 || j >= 0 || carry) {
            if (i >= 0) carry += a[i--] - '0';
            if (j >= 0) carry += b[j--] - '0';
            ans += '0' + (carry & 1);
            carry >>= 1;
        }
        return string(rbegin(ans), rend(ans));
    }
};