Tech Blogs LLD SDE Playbook DSA

Add Binary

Easy Top 250
Associated Patterns
Bit Manipulation
Interviewed At (Company Tags)
FacebookAmazonGoogle
External Reference View on LeetCode

Problem Description

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

Examples

Example 1:

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

Example 2:

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

Constraints

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

Column-by-Column Addition with Carry

Add digits from right to left, tracking a carry. At each position:

  1. sum = bit_a + bit_b + carry
  2. current bit = sum % 2
  3. carry = sum / 2

Keep a string builder or array to accumulate the result, and reverse it at the end.

Solution: Schoolbook Addition

class Solution {
    public String addBinary(String a, String b) {
        StringBuilder sb = new StringBuilder();
        int i = a.length() - 1, j = b.length() - 1, carry = 0;

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

        return sb.reverse().toString();
    }
}
class Solution:
    def addBinary(self, a: str, b: str) -> str:
        result = []
        i, j, carry = len(a) - 1, len(b) - 1, 0

        while i >= 0 or j >= 0 or carry:
            total = carry
            if i >= 0:
                total += int(a[i])
                i -= 1
            if j >= 0:
                total += int(b[j])
                j -= 1
            result.append(str(total % 2))
            carry = total // 2

        return "".join(reversed(result))
#include <string>
#include <algorithm>

class Solution {
public:
    std::string addBinary(std::string a, std::string b) {
        std::string result = "";
        int i = a.size() - 1, j = b.size() - 1, carry = 0;

        while (i >= 0 || j >= 0 || carry) {
            int sum = carry;
            if (i >= 0) sum += a[i--] - '0';
            if (j >= 0) sum += b[j--] - '0';
            result += std::to_string(sum % 2);
            carry = sum / 2;
        }

        std::reverse(result.begin(), result.end());
        return result;
    }
};

Complexity Analysis:

  • Time Complexity: O(max(N, M)) where N and M are the lengths of a and b. We do constant time work for each character.
  • Space Complexity: O(max(N, M)) to store the output string.

← All Problems