Add Binary
EasyPrompt
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.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach leverages Java's BigInteger class, which is designed to handle arbitrarily large integers. The core idea is to convert the input binary strings into BigInteger objects, use the class's built-in addition functionality, and then convert the result back to a binary string. This method is straightforward and relies on powerful, pre-existing library features.
Algorithm
- Convert the first binary string
ainto aBigIntegerobject, specifying the base (radix) as 2. - Convert the second binary string
binto anotherBigIntegerobject, also with radix 2. - Use the
add()method of theBigIntegerclass to compute the sum of the two numbers. - Convert the resulting
BigIntegersum back into a binary string representation using thetoString()method with radix 2. - Return the final binary string.
Walkthrough
Java's java.math.BigInteger class is perfect for arithmetic operations on numbers that are too large to fit into standard primitive types like long. Since the input strings can be up to 10<sup>4</sup> characters long, they represent numbers far exceeding the capacity of a 64-bit long.
The steps are as follows:
- Instantiate a
BigIntegerfrom stringausing the constructornew BigInteger(a, 2), where2indicates that the string is in base-2 (binary). - Do the same for string
b. - Call the
.add()method on oneBigIntegerobject, passing the other as an argument. This returns a newBigIntegerobject holding the sum. - Call
.toString(2)on the resultingBigIntegerto get its binary string representation.
import java.math.BigInteger; class Solution { public String addBinary(String a, String b) { // Convert binary strings to BigInteger BigInteger numA = new BigInteger(a, 2); BigInteger numB = new BigInteger(b, 2); // Add the two BigIntegers BigInteger sum = numA.add(numB); // Convert the result back to a binary string return sum.toString(2); }}Complexity
Time
O(max(N, M))
Space
O(max(N, M))
Trade-offs
Pros
Extremely simple and concise to write, leading to less development time.
Reduces the chance of implementation errors by using a well-tested, robust library.
The code is highly readable and self-explanatory.
Cons
May not be permitted in an interview setting, as it abstracts away the core logic of binary addition which is often the main point of the question.
Introduces a dependency on a specific library (
java.math.BigInteger), which might not be available in all programming environments.Can have performance overhead due to object creation, string parsing, and method calls compared to a direct, manual implementation.
This approach simulates the manual, grade-school process of adding two numbers column by column, from right to left (least significant bit to most significant bit). We iterate through the strings from their ends, adding the corresponding bits along with a carry from the previous column. The result is built one bit at a time, and since we build it from right-to-left, the resulting string needs to be reversed at the end.
Algorithm
- Initialize an empty
StringBuilderto build the result string and set an integercarryto 0. - Initialize two pointers,
iandj, to point to the last character of stringsaandbrespectively. - Loop as long as there are digits left in either string or there is a carry (
i >= 0 || j >= 0 || carry > 0). - In each iteration, calculate the
sumfor the current position by addingcarryto the digits ata[i]andb[j], if they exist. - The current result bit is
sum % 2. Append this bit to theStringBuilder. - The new
carryfor the next position issum / 2. - Decrement the pointers
iandj. - After the loop, the
StringBuildercontains the sum in reverse order. Reverse it and convert to a string to get the final answer.
Walkthrough
This is the fundamental approach that solves the problem from first principles. We manage the state of the addition manually with a carry variable and pointers for the current position in each string.
The algorithm proceeds as follows:
- We use a
StringBuilderfor efficient string construction, as repeated string concatenation in a loop is inefficient. - We start from the end of both strings, which corresponds to the least significant bit.
- The loop continues as long as we have digits to process in either string (
i >= 0orj >= 0) or if there's a remainingcarryfrom the most significant bit's addition. - Inside the loop, we calculate the
sumfor the current bit position. We startsumwith thecarryfrom the previous position. We add the integer value of the characters fromaandbif the respective pointers are still valid. Note thatchar '1' - char '0'gives the integer1. - The binary digit for the current position is the remainder of the sum when divided by 2 (
sum % 2). This is appended to our result. - The carry to be used in the next (more significant) position is the result of integer division by 2 (
sum / 2). - Finally, since we appended bits from right to left, our
StringBuilderis in reverse order. We call.reverse()before returning the final string.
class Solution { public String addBinary(String a, String b) { StringBuilder result = new StringBuilder(); int i = a.length() - 1; int j = b.length() - 1; int carry = 0; while (i >= 0 || j >= 0 || carry > 0) { int sum = carry; if (i >= 0) { sum += a.charAt(i) - '0'; i--; } if (j >= 0) { sum += b.charAt(j) - '0'; j--; } result.append(sum % 2); carry = sum / 2; } return result.reverse().toString(); }}Complexity
Time
O(max(N, M))
Space
O(max(N, M))
Trade-offs
Pros
Highly efficient with minimal overhead, as it only uses basic arithmetic and string building operations.
Demonstrates a strong understanding of fundamental binary arithmetic and algorithms.
It is self-contained and does not rely on any special libraries for the core logic.
Cons
More complex and verbose to implement compared to using a built-in library.
There is a higher chance of logical errors, such as off-by-one errors with pointers or incorrect handling of the carry.
Solutions
Solution
class Solution {public String addBinary(String a, String b) { var sb = new StringBuilder(); int i = a.length() - 1, j = b.length() - 1; for (int carry = 0; i >= 0 || j >= 0 || carry > 0; --i, --j) { carry += (i >= 0 ? a.charAt(i) - '0' : 0) + (j >= 0 ? b.charAt(j) - '0' : 0); sb.append(carry % 2); carry /= 2; } return sb.reverse().toString(); }}public class Solution { public string AddBinary(string a, string b) { int i = a.Length - 1; int j = b.Length - 1; var sb = new StringBuilder(); for (int carry = 0; i >= 0 || j >= 0 || carry > 0; --i, --j) { carry += i >= 0 ? a[i] - '0' : 0; carry += j >= 0 ? b[j] - '0' : 0; sb.Append(carry % 2); carry /= 2; } var ans = sb.ToString().ToCharArray(); Array.Reverse(ans); return new string(ans); }}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])class Solution {public: string addBinary(string a, string b) { string ans; int i = a.size() - 1, j = b.size() - 1; for (int carry = 0; i >= 0 || j >= 0 || carry; --i, --j) { carry += (i >= 0 ? a[i] - '0' : 0) + (j >= 0 ? b[j] - '0' : 0); ans.push_back((carry % 2) + '0'); carry /= 2; } reverse(ans.begin(), ans.end()); return ans; }};Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.