Add Binary

EASY

Description

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 <= 10⁴
a and b consist only of '0' or '1' characters.
Each string does not contain leading zeros except for the zero itself.

Approaches

Checkout 2 different approaches to solve Add Binary. Click on different approaches to view the approach and algorithm in detail.

Using Built-in BigInteger

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 a into a BigInteger object, specifying the base (radix) as 2.
Convert the second binary string b into another BigInteger object, also with radix 2.
Use the add() method of the BigInteger class to compute the sum of the two numbers.
Convert the resulting BigInteger sum back into a binary string representation using the toString() method with radix 2.
Return the final binary string.

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 BigInteger from string a using the constructor new BigInteger(a, 2), where 2 indicates that the string is in base-2 (binary).
Do the same for string b.
Call the .add() method on one BigInteger object, passing the other as an argument. This returns a new BigInteger object holding the sum.
Call .toString(2) on the resulting BigInteger to 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 Analysis

Time Complexity: O(max(N, M))Space Complexity: O(max(N, M))

Pros and Cons

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.

Code Solutions

Checking out 4 solutions in different languages for Add Binary. Click on different languages to view the code.

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();
  }
}

Video Solution

Watch the video walkthrough for Add Binary

Patterns:

MathBit Manipulation

Data Structures:

String

Companies:

Adobe |Amazon |Apple |Bloomberg |