Add Binary - Leetcode Solution

Problem Link

💡 Step-by-Step Thought Process

Understand the problem: Add two binary strings and return their sum as a binary string.
Convert the binary strings a and b to integers using base-2 conversion.
While b is not zero, perform binary addition without converting to decimal:
Compute the sum without carry using XOR (a ^ b).
Compute the carry using AND (a & b) and left-shift it by 1.
Update a to the sum without carry and b to the carry.
Convert the final integer a to a binary string, removing the "0b" prefix, and return it.

Code Solution

class Solution:
    def addBinary(self, a, b) -> str:
        a, b = int(a, 2), int(b, 2)
        
        while b:
            without_carry = a ^ b
            carry = (a & b) << 1
            a, b = without_carry, carry
            
        return bin(a)[2:]
        # Time: O(A + B)
        # Space: O(1)

class BigInt {
private:
    string binary;

    // Helper function to ensure strings are the same length
    static void equalizeLength(string& a, string& b) {
        int lengthDifference = a.size() - b.size();
        if (lengthDifference > 0)
            b.insert(0, lengthDifference, '0');
        else
            a.insert(0, -lengthDifference, '0');
    }

    // Helper function to remove leading zeros
    void removeLeadingZeros() {
        // Erase leading zeros while keeping at least one zero if the number is
        // zero
        auto firstNonZero = binary.find_first_not_of('0');
        if (firstNonZero != string::npos) {
            binary.erase(0, firstNonZero);
        } else {
            binary =
                "0";  // Adjust to maintain a minimum representation of zero
        }
    }

public:
    BigInt() : binary("0") {}

    // Constructor from a binary string
    BigInt(const string& bin) : binary(bin) { removeLeadingZeros(); }

    // Bitwise XOR
    BigInt operator^(const BigInt& other) const {
        string a = binary;
        string b = other.binary;
        equalizeLength(a, b);
        string result;
        for (size_t i = 0; i < a.size(); i++) {
            char xorChar = (a[i] == b[i] ? '0' : '1');
            result.push_back(xorChar);
        }
        return BigInt(result);
    }

    // Bitwise AND
    BigInt operator&(const BigInt& other) const {
        string a = binary;
        string b = other.binary;
        equalizeLength(a, b);
        string result;
        for (size_t i = 0; i < a.size(); i++) {
            char andChar = (a[i] == '1' && b[i] == '1' ? '1' : '0');
            result.push_back(andChar);
        }
        return BigInt(result);
    }

    // Left shift
    BigInt operator<<(int shift) const {
        string result = binary;
        result.append(shift, '0');
        return BigInt(result);
    }

    // Check if BigInt is zero
    bool isZero() const {
        for (char c : binary)
            if (c != '0') return false;
        return true;
    }

    // Getter for binary string
    string getBinary() const { return binary; }
};

class Solution {
public:
    string addBinary(string a, string b) {
        BigInt x(a);
        BigInt y(b);
        BigInt carry, answer;

        while (!y.isZero()) {
            answer = x ^ y;
            carry = (x & y) << 1;
            x = answer;
            y = carry;
        }
        return x.getBinary();
    }
};

import java.math.BigInteger;

public class Solution {
    public String addBinary(String a, String b) {
        // Convert the binary strings to BigInteger
        BigInteger x = new BigInteger(a, 2);
        BigInteger y = new BigInteger(b, 2);

        // Perform the binary addition using bitwise operations
        while (y.compareTo(BigInteger.ZERO) != 0) {
            BigInteger withoutCarry = x.xor(y);
            BigInteger carry = x.and(y).shiftLeft(1);
            x = withoutCarry;
            y = carry;
        }

        // Convert the result back to binary and return it as a string
        return x.toString(2);
    }
}

var addBinary = function(a, b) {
    // Convert the binary strings to BigInt
    let x = BigInt("0b" + a);
    let y = BigInt("0b" + b);

    // Perform the binary addition using bitwise operations
    while (y !== 0n) {
        let withoutCarry = x ^ y;
        let carry = (x & y) << 1n;
        x = withoutCarry;
        y = carry;
    }

    // Convert the result back to binary and return it as a string
    return x.toString(2);
};

Detailed Explanation

Understanding the Add Binary Problem

The Add Binary problem requires performing binary addition on two input strings representing binary numbers. This is a classic bit manipulation task that mimics how addition works at the binary level, making it particularly relevant for technical interviews and low-level programming.

The goal is to return the sum of these binary numbers as a string, without converting them to integers in a naïve or language-specific way. This ensures we build a solution that handles large inputs that could overflow integer limits in some environments.

Strategy for Adding Binary Strings

A straightforward and effective way to solve this is to simulate binary addition using a loop. Start by initializing two pointers at the end of each binary string. Loop through both strings from right to left, adding the corresponding bits along with a carry value. Append the result of each bit addition to a list, which is reversed at the end to produce the final binary string.

Alternatively, for a more elegant and performant solution, you can convert the strings to integers using base-2 conversion and use bitwise operations to simulate binary addition:

XOR (a ^ b): Adds the bits without considering the carry.
AND (a & b) << 1: Calculates the carry by identifying positions where both bits are 1, and shifts it left for the next position.
Repeat until there’s no carry left (i.e., b becomes 0).

Finally, convert the result back to a binary string and remove the "0b" prefix that comes from Python’s binary format.

Time and Space Complexity

Time Complexity: O(max(m, n)), where m and n are the lengths of the input strings. Each bit is processed once.
Space Complexity: O(max(m, n)), as the output string or list storing the result will grow with the size of the inputs.

Why This Approach Works

This approach mimics the exact process used in hardware and low-level programming for binary addition, making it extremely efficient. The use of XOR and AND for summing and carrying ensures constant-time operations on each bit, which scales linearly with input size. It also avoids the need for string-to-integer conversion in languages that don't support big integers.

Conclusion

Solving the Add Binary problem improves your understanding of bitwise operations, carry propagation, and string manipulation. It’s a foundational problem that paves the way for mastering binary math, bit manipulation algorithms, and efficient number processing in memory-constrained systems.

Get Personalized Support at AlgoMap Bootcamp 💡