progress

~/problems / Bit manipulation

Add Binary

On a phone? Coding is easier on a laptop: email this problem to yourself . Meanwhile: quiz this topic or fight a boss.

easy ~15 min

Two counters report their values as binary strings, most significant digit first, often too long for any built-in integer type in C++ or Java.

Write add_binary(a: str, b: str) -> str: their sum as a binary string with no leading zeros (zero is "0").

add_binary("1011", "111")   # "10010"   (11 + 7 = 18)
add_binary("1", "1")        # "10"
add_binary("0", "0")        # "0"
add_binary("100", "0")      # "100"

Each string has up to 5 * 10^5 digits and is "0" or starts with '1'. Work digit by digit rather than converting whole strings into numbers.

⭐ Bonus: a speed test with 500,000-digit strings earns a star in O(len(a) + len(b)). Adding a character to the front of a string each step copies it every time, which is quadratic.

Show hint

do it as on paper: from the right, keep a carry of 0 or 1, emit one digit per column, and reverse once at the end.

Topic: Bit manipulation (IP / CIDR). IPv4 as a 32-bit int; lowest set bit for block sizes.

Read the visual guide
0:00
Ctrl ' run · Ctrl ↵ submit
esc