Skip to content
LEETFLIX

Add Binary

EasyMathStringBitmask
Solve on LeetCode

Easy · binary add with carry. Real solution for this problem — same player as the hand-authored deep-dives.

01

Problem

Read the prompt, flip through the examples, then steal the idea.

LeetCode 67. Add Binary. The copyrighted prompt is on LeetCode. This page is a working binary add with carry for this problem: editable input, Python, Go, and a step-by-step animation.

Constraints

  • —Player inputs are capped so the animation stays readable.
  • —Match LeetCode's own constraints when you submit there.

Examples

Input

a =
11
b =
1

Output

100

02

Solution

Python and Go. The walkthrough below runs this same code.

Approach 1Optimal▶ Animated

Add from the right, keep a carry

Same as Add Two Numbers, but the digits are bits. sum % 2 is the written bit; sum // 2 is the carry.

Walk both strings from the end. A leftover carry becomes a leading 1.

Algorithm

  1. i, j at the last characters, carry = 0.
  2. While either string or the carry remains, write sum % 2 and keep sum // 2.
  3. Reverse the collected bits.
Time
O(n)
Space
O(n)
Solution.py
class Solution:    def addBinary(self, a: str, b: str) -> str:        i, j, carry = len(a) - 1, len(b) - 1, 0        out: list[str] = []        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))
Watch this run

03

Interactive walkthrough

Playing “Add from the right, keep a carry”. Edit the input, hit Run, then scrub.

Approach: Add from the right, keep a carry

Loading animation…