Add Binary - Solution & Explanation
Problem Statement
Given two binary strings a and b, return their sum as a binary string.
Example 1:
Input: a = "11", b = "1" Output: "100"
Example 2:
Input: a = "1010", b = "1011" Output: "10101"
Constraints:
1 <= a.length, b.length <= 104aandbconsist only of'0'or'1'characters.- Each string does not contain leading zeros except for the zero itself.
Approach Overview
Problem Overview: You are given two binary strings a and b. Add them together and return the result as a binary string. The challenge is handling binary addition rules (0+0, 0+1, 1+1) and propagating the carry correctly across digits.
Approach 1: Bit-by-Bit Addition with Carry (Time: O(n), Space: O(n))
This approach simulates the same process you use when adding numbers by hand. Start from the rightmost digits of both strings and move left. At each step, convert the current characters to integers, add them with a carry, compute the resulting bit using sum % 2, and update the carry using sum // 2. Append the computed bit to a result builder and continue until both strings and the carry are exhausted. Since you scan each digit once, the time complexity is O(n) where n is the length of the longer string, and space complexity is O(n) for the output string. This method directly uses concepts from math and bit manipulation while treating the process as a simple string traversal.
Approach 2: Using Built-in Big Integer Libraries (Time: O(n), Space: O(n))
Some languages provide built-in support for large integers that can parse binary strings directly. Convert both binary strings into integers using base-2 parsing, perform a normal integer addition, and convert the result back to a binary string. For example, Python's int(a, 2) or Java's BigInteger can handle arbitrarily large values. The time complexity remains O(n) due to parsing and conversion, and space complexity is O(n) for the resulting binary representation. This approach is concise and readable but relies on language features rather than demonstrating algorithmic understanding.
Recommended for interviews: The bit-by-bit addition approach is the one interviewers expect. It shows you understand binary arithmetic, carry propagation, and efficient string traversal. The big integer approach works in production code when readability matters, but it hides the underlying logic that interviewers typically want to evaluate.
Approach 1: Bit-by-Bit Addition with Carry
This method involves simulating the addition process as if one were adding numbers on paper. We traverse both strings from the least significant bit to the most, adding corresponding bits and maintaining a carry as needed. If the carry is still 1 after processing both strings, it is added to the result.
The code declares an array result to hold the final binary string, iterates through the input strings from the end to the start, calculates the bit sum while considering a carry, and builds the result string by adjusting the index with a carry sum. The final output is the result trimmed to exclude leading zeros.
Complexity
Time Complexity: O(max(N, M)) where N and M are the lengths of strings a and b. The space complexity is also O(max(N, M)) to store the result.
Approach 2: Using Built-in Big Integer Libraries
This approach leverages built-in support for manipulating large integers available in many programming languages. By converting binary strings to integers, performing arithmetic operations, and then converting the result back to binary format, we can simplify the computation.
This Python solution uses the int function to convert binary strings to integers, adds them, and converts the sum back to binary format using the bin function, stripping the '0b' prefix with slicing.
Code
Python
Java
JavaScript
Complexity
Time Complexity: O(N + M), due to integer conversion and addition operations. Space Complexity: O(N + M) for storing integer representations.
Approach 3: Simulation
We use a variable carry to record the current carry, and two pointers i and j to point to the end of a and b respectively, and add them bit by bit from the end to the beginning.
The time complexity is O(max(m, n)), where m and n are the lengths of strings a and b respectively. The space complexity is O(1).
Complexity Comparison
| Approach | Complexity |
|---|---|
| Bit-by-Bit Addition with Carry | Time Complexity: O(max(N, M)) where N and M are the lengths of strings |
| Using Built-in Big Integer Libraries | Time Complexity: O(N + M), due to integer conversion and addition operations. Space Complexity: O(N + M) for storing integer representations. |
| Simulation | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Bit-by-Bit Addition with Carry | O(n) | O(n) | Best for interviews and when implementing binary addition logic manually |
| Built-in Big Integer Conversion | O(n) | O(n) | When the language provides reliable big integer parsing and concise code is preferred |
Video Solution
Add Binary - Leetcode 67 - Python • NeetCode • 93,293 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Add Binary easy or hard?
Add Binary Python/Java solution
How to solve Add Binary in O(n)?
What is the best approach for Add Binary?
Is Add Binary asked at Google/Amazon/Meta?
What data structure is used in Add Binary?
What is the time complexity of Add Binary?
Ready to solve this problem?
Practice Add Binary with our built-in code editor and test cases.
Practice on FleetCode