EasyNo. 0067
Add Binary — LeetCode 67 Python Solution
- Pattern
- Bit Manipulation
- Topics
- Bit Manipulation, Math, String, Simulation
- On study lists
- Grind 75 and Top Interview 150
- Reading time
- 2 min
- Source
- leetcode.com
The problem
Given two binary strings a and b, return their sum as a binary string.
Example
- Input
- a = "11", b = "1"
- Output
- "100"
Python solution
class Solution:
def addBinary(self, a: str, b: str) -> str:
ans = []
i, j, carry = len(a) - 1, len(b) - 1, 0
while i >= 0 or j >= 0 or carry:
carry += (0 if i < 0 else int(a[i])) + (0 if j < 0 else int(b[j]))
carry, v = divmod(carry, 2)
ans.append(str(v))
i, j = i - 1, j - 1
return "".join(ans[::-1])Complexity
- Time
- O(max(m, n))where m and n are the lengths of strings a and b respectively
- Space · auxiliary
- O(1)
Pattern: Bit Manipulation
Use XOR, masks and the low-bit trick to replace whole data structures with an integer. LeetCode 67. Add Binary is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Bit Manipulation.
The bit manipulation guide has the Python template for the pattern and the 194 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0405 | Convert a Number to Hexadecimal | Easy |
| 1404 | Number of Steps to Reduce a Number in Binary Representation to One | Medium |
| 1680 | Concatenation of Consecutive Binary Numbers | Medium |
| 0029 | Divide Two Integers | Medium |
| 0231 | Power of Two | Easy |
| 0318 | Maximum Product of Word Lengths | Medium |
Frequently asked questions
- How hard is LeetCode 67. Add Binary?
LeetCode 67. Add Binary is rated Easy on LeetCode.
- What is the time complexity of LeetCode 67. Add Binary?
The Python solution on this page runs in O(max(m, n)), where m and n are the lengths of strings a and b respectively.
- What is the space complexity of LeetCode 67. Add Binary?
The Python solution on this page uses O(1) auxiliary space.
- What topics does LeetCode 67. Add Binary cover?
LeetCode 67. Add Binary is tagged Bit Manipulation, Math, String and Simulation on LeetCode.