# Add Binary
**Difficulty:** EASY
[External](https://leetcode.com/problems/add-binary)
Canonical: https://scaleengineer.com/dsa/problems/add-binary
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Data structures:** String
**Companies:** [Adobe](https://scaleengineer.com/companies/adobe), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [Google](https://scaleengineer.com/companies/google), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Uber](https://scaleengineer.com/companies/uber), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [tcs](https://scaleengineer.com/companies/tcs), [SIG](https://scaleengineer.com/companies/sig)
---
## Problem
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
## 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.
**Time:** O(max(N, M)) · **Space:** O(max(N, M))
**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.
### Explanation
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.

```java
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);
    }
}
```
### 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.

## Bit-by-Bit Simulation
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.
**Time:** O(max(N, M)) · **Space:** O(max(N, M))
**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.
### Explanation
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:
1.  We use a `StringBuilder` for efficient string construction, as repeated string concatenation in a loop is inefficient.
2.  We start from the end of both strings, which corresponds to the least significant bit.
3.  The loop continues as long as we have digits to process in either string (`i >= 0` or `j >= 0`) or if there's a remaining `carry` from the most significant bit's addition.
4.  Inside the loop, we calculate the `sum` for the current bit position. We start `sum` with the `carry` from the previous position. We add the integer value of the characters from `a` and `b` if the respective pointers are still valid. Note that `char '1' - char '0'` gives the integer `1`.
5.  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.
6.  The carry to be used in the next (more significant) position is the result of integer division by 2 (`sum / 2`).
7.  Finally, since we appended bits from right to left, our `StringBuilder` is in reverse order. We call `.reverse()` before returning the final string.

```java
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();
    }
}
```
### Algorithm
- Initialize an empty `StringBuilder` to build the result string and set an integer `carry` to 0.
- Initialize two pointers, `i` and `j`, to point to the last character of strings `a` and `b` respectively.
- 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 `sum` for the current position by adding `carry` to the digits at `a[i]` and `b[j]`, if they exist.
- The current result bit is `sum % 2`. Append this bit to the `StringBuilder`.
- The new `carry` for the next position is `sum / 2`.
- Decrement the pointers `i` and `j`.
- After the loop, the `StringBuilder` contains the sum in reverse order. Reverse it and convert to a string to get the final answer.

# Solutions
### Java

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

```

### CSharp

```csharp
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);
    }
}
```

### Python

```python
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])

```

### CPP

```cpp
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;
  }
};

```