Add Binary

EASY✓ CHIP-TIMEDLC #67 — FULL STATEMENT ↗

The drill: Add two binary strings the way you'd add on paper — digit by digit from the right, carrying into the next column — and hand back the binary sum as a string.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

Two strings arrive, each spelled only with the characters 0 and 1 and possibly of different lengths, representing two binary numbers to be added together.

The result comes back as a single binary string holding their sum — no leading zero should pad the answer, unless the sum itself is exactly zero, in which case a single 0 is correct.

Lengths of the two inputs can differ freely, and the shorter one runs out of digits before the longer one, so any leftover carry has to keep propagating through the remaining digits alone.

EX 01

a = "11" · b = "1"

→ "100"

CARRY RIPPLES ALL THE WAY THROUGH

EX 02

a = "1010" · b = "1011"

→ "10101"

SAME LENGTH OPERANDS

EX 03

a = "0" · b = "0"

→ "0"

ZERO PLUS ZERO

both inputs are non-empty strings made only of '0' and '1' characters
the two strings may differ in length, up to roughly ten thousand characters each
the output must not carry a leading zero, except the single-character "0"
inputs never contain a sign character, whitespace, or other digits

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Converting both strings to numbers and adding them works today, but it leans on a library doing arithmetic no different from what you'd do by hand.

HINT 2 THE STRUCTURE

Binary addition is grade-school addition in base 2: walk both strings from the last character, sum the two digits plus whatever carried in.

HINT 3 ONE STEP FROM THE ANSWER

At each column: total = digitA + digitB + carry. Write total % 2, carry forward total / 2. Keep going past the shorter string as long as a carry remains.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE COLUMN CARRYPATTERN · CARRY SIMULATIONa = "1101" · b = "101"

STEP 1

Two binary strings, right-aligned: 1101 and 101. Walk from the last column, summing digit + digit + carry.

STEP 1 / 7 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/add-binary.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        i, j = len(a) - 1, len(b) - 1
        carry = 0
        out = []
        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
            out.append(str(total % 2))
            carry = total // 2
        return "".join(reversed(out))

TIME O(MAX(M, N))SPACE O(MAX(M, N))PYTHON · RACE PACE · 16 LN

class Solution {
    public String addBinary(String a, String b) {
        StringBuilder out = new StringBuilder();
        int i = a.length() - 1;
        int j = b.length() - 1;
        int carry = 0;
        while (i >= 0 || j >= 0 || carry != 0) {
            int total = carry;
            if (i >= 0) {
                total += a.charAt(i--) - '0';
            }
            if (j >= 0) {
                total += b.charAt(j--) - '0';
            }
            out.append(total % 2);
            carry = total / 2;
        }
        return out.reverse().toString();
    }
}

TIME O(MAX(M, N))SPACE O(MAX(M, N))JAVA · RACE PACE · 20 LN

class Solution {
    public String addBinary(String a, String b) {
        long total = Long.parseLong(a, 2) + Long.parseLong(b, 2);
        return Long.toBinaryString(total);
    }
}

TIME O(N)SPACE O(N)JAVA · TRAINING PACE · 6 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED