Add Binary

NeetCode: Add Binary · LeetCode: 67. Add Binary · Difficulty: Easy

Given two binary strings a and b, return their sum as a binary string. The strings can be far longer than any machine integer.

Example

Text

Input:  a = "11", b = "1"          Output: "100"
Input:  a = "1010", b = "1011"     Output: "10101"

Brute force: convert to integers

Parse both strings into integers, add, and print the sum in base 2. It is short, but only correct while the values fit. Long.parseLong(s, 2) handles inputs up to 63 bits and throws NumberFormatException for a longer string. Math.addExact throws ArithmeticException when the sum overflows, where a plain + would wrap silently. The constraints allow up to 10^4 digits. The method returns null when the input does not fit. (java.math.BigInteger accepts a radix too, as in new BigInteger(a, 2), and has no size limit, but the digit loop below is the algorithm the problem asks for.)

Java

class Solution {
    // Returns null when an input or the sum does not fit in a long.
    public String addBinary(String a, String b) {
        try {
            long x = Long.parseLong(a, 2);
            long y = Long.parseLong(b, 2);
            long sum = Math.addExact(x, y);
            return Long.toBinaryString(sum);
        } catch (NumberFormatException | ArithmeticException e) {
            return null;
        }
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.addBinary("11", "1"));
        System.out.println(s.addBinary("1010", "1011"));
        System.out.println(s.addBinary("0", "0"));
        String tooLong = "1".repeat(200);
        System.out.println(s.addBinary(tooLong, "1")); // too long for a long
    }
}

Output

100
10101
0
null

Time: O(n) for parsing. Space: O(n). Limited to 63-bit inputs.

Optimal: schoolbook addition with a carry

Add the way you do on paper: start from the least significant digits, add the two digits plus the carry, output sum % 2 and carry sum / 2. Keep going until both strings are exhausted and the carry is zero. Digits are produced least significant first, so a StringBuilder collects them and reverse() fixes the order at the end. The indices start at the last character of each string and count down. A negative index means that string has no digits left. charAt(i) - '0' turns the character '0' or '1' into the int 0 or 1, because char arithmetic works on the 16-bit code values.

Java

class Solution {
    public String addBinary(String a, String b) {
        int i = a.length() - 1;
        int j = b.length() - 1;
        int carry = 0;
        StringBuilder out = new StringBuilder();
        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';
            }
            out.append(sum % 2);
            carry = sum / 2;
        }
        if (out.length() == 0) {
            out.append('0');
        }
        return out.reverse().toString();
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.addBinary("11", "1"));
        System.out.println(s.addBinary("1010", "1011"));
        System.out.println(s.addBinary("0", "0"));
        String tooLong = "1".repeat(200);
        String r = s.addBinary(tooLong, "1");
        System.out.println(r.length() + " " + r.substring(0, 3));
    }
}

Output

Time: O(max(m, n)). Space: O(max(m, n)) for the result.

Edge cases

"0" + "0" runs the loop once and produces "0"; the out.length() == 0 guard applies only to empty inputs, which the constraints exclude.
The last line of main adds 1 to 200 ones, giving 2^200: a 1 followed by 200 zeros, 201 digits.