Add Binary
The key idea
Add the two strings the way you add numbers on paper: walk both from the rightmost digit to the left, sum the matching bits plus a running carry, write down
sum % 2 as the next result bit, and roll sum // 2 into the carry. After both strings are exhausted, if a carry remains, it becomes the leading bit.Problem
You are given two binary strings a and b. Return their sum as a binary string. The result must itself be a binary string, so each character is '0' or '1', and you should add the two inputs without converting them to integers, since they can be far too long to fit in a fixed-width number.
Constraints
- 1 <= a.length, b.length <= 10^4
- a and b consist only of the characters '0' or '1'
- Each string does not contain leading zeros except for the value "0" itself
Examples
Input: a = "11", b = "1"
Output: "100"
Input: a = "1010", b = "1011"
Output: "10101"
Complexity
Time: O(max(m, n)) Space: O(max(m, n))
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Math / Number Theory problems
- Factorial Trailing ZeroesMEDIUM
- Excel Sheet Column TitleEASY
- Greatest Common Divisor of StringsEASY
- Integer to RomanMEDIUM
- Multiply StringsMEDIUM
- Palindrome NumberEASY
- Plus OneEASY
- Reverse IntegerMEDIUM
- Roman to IntegerEASY