Add Binary

Easy#67bit by bit

You get two binary numbers written as strings of 0s and 1s, maybe of different lengths. Return their sum, also as a binary string. Our example: a = "1101" and b = "111" — the answer is "10100", that is 13 + 7 = 20.

67 Add BinaryWalkthrough · 1×

Example: a = "1101", b = "111". Column addition from the right; the top row is the carry into each column.

carrya1101= 13b111= 7out—
not added yetthe current column; the digit just writtenadded; a known carrythe carry just made for the next columnthe sum

i and j start at the last digits, the lowest bits: a[3] = 1 and b[2] = 1

01/39
restart · back · play · step
Speed
1function addBinary(a, b):
2 i = len(a) - 1; j = len(b) - 1
3 carry = 0; out = ""
4 while i >= 0 or j >= 0 or carry == 1:
5 sum = carry
6 if i >= 0: sum = sum + a[i]
7 if j >= 0: sum = sum + b[j]
8 out = (sum & 1) + out
9 carry = sum >> 1
10 i = i - 1; j = j - 1
11 return out
state
i
3
j
2
carry
–
sum
–
out
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. A column adds at most three ones: two digits and the carry, so sum is 0, 1, 2 or 3, which is 00, 01, 10 or 11. Its low bit, sum & 1, is the digit of the answer, and the bit above it, sum >> 1, is the carry.
  2. A number that runs out simply adds 0, so a and b may have any lengths and the shorter one needs no padding.
  3. The loop also runs while carry = 1: in our example the last carry turns into the leading 1, and the answer is a digit longer than both numbers.

Complexity

Time O(n + m): one pass over the digits of a and b, plus at most one more column for the last carry. Memory O(max(n, m)) for the answer itself; everything else is a few numbers.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.