Scale Engineer

Add Binary

Easy
#0067Time: O(max(N, M))Space: O(max(N, M))11 companies
Patterns
MathBit Manipulation
Data structures
String
Companies
AdobeAmazonAppleBloomberg

Prompt

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 <= 104
  • a and b consist 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 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.

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:

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

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.

Solutions

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 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.

← Previous

Previous problem

Next →

Next problem