Add Binary
Add Binary is a easy arrays & hashing problem solved with the right to left traversal pattern.
The best approach, optimal (two pointers from the right), runs in O(max(n, m)) time and O(max(n, m)) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (pad and prepend) up.
Problem
You are given two strings a and b, each holding a non-negative integer written in binary. Return their sum, also as a binary string.
The strings can be thousands of digits long, so converting them to a built-in integer type will overflow; add them digit by digit instead.
Examples
Example 1
- Input
a = "1101", b = "111"- Output
"10100"- Why
- 13 + 7 = 20, and 20 in binary is 10100.
Example 2
- Input
a = "0", b = "1011"- Output
"1011"- Why
- Adding zero leaves the other number unchanged.
Example 3
- Input
a = "1", b = "1"- Output
"10"- Why
- 1 + 1 = 2, which needs a new leading digit.
Constraints
1 <= a.length, b.length <= 10^4aandbcontain only the characters'0'and'1'.- Neither string has leading zeros, except the number zero itself, written
"0".
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (pad and prepend) | O(n²) | O(n) |
| Optimal (two pointers from the right) | O(max(n, m)) | O(max(n, m)) |
1Brute force (pad and prepend)
O(n²)Each of the n prepends copies the partial result, which is up to n characters long.O(n)The padded copies and the result string.Pad the shorter string with leading zeros so both have the same length, then add column by column from the right. Each result digit is placed in front of the answer built so far, which copies the whole string every time.
- Left-pad the shorter string with '0' until both lengths are equal.
- Walk i from the last index to 0, compute sum = a[i] + b[i] + carry.
- Set result = (sum % 2) + result and carry = sum / 2.
- If a carry is left at the end, put '1' in front.
class Solution {
public String addBinary(String a, String b) {
int n = Math.max(a.length(), b.length());
while (a.length() < n) a = "0" + a;
while (b.length() < n) b = "0" + b;
String result = "";
int carry = 0;
for (int i = n - 1; i >= 0; i--) {
int sum = (a.charAt(i) - '0') + (b.charAt(i) - '0') + carry;
result = (sum % 2) + result;
carry = sum / 2;
}
if (carry == 1) result = "1" + result;
return result;
}
}class Solution:
def addBinary(self, a: str, b: str) -> str:
n = max(len(a), len(b))
a = a.rjust(n, "0")
b = b.rjust(n, "0")
result = ""
carry = 0
for i in range(n - 1, -1, -1):
total = int(a[i]) + int(b[i]) + carry
result = str(total % 2) + result
carry = total // 2
if carry:
result = "1" + result
return resultclass Solution {
public:
string addBinary(string a, string b) {
int n = max(a.size(), b.size());
while ((int)a.size() < n) a = "0" + a;
while ((int)b.size() < n) b = "0" + b;
string result = "";
int carry = 0;
for (int i = n - 1; i >= 0; i--) {
int sum = (a[i] - '0') + (b[i] - '0') + carry;
result = char('0' + sum % 2) + result;
carry = sum / 2;
}
if (carry == 1) result = "1" + result;
return result;
}
};function addBinary(a, b) {
const n = Math.max(a.length, b.length);
a = a.padStart(n, "0");
b = b.padStart(n, "0");
let result = "";
let carry = 0;
for (let i = n - 1; i >= 0; i--) {
const sum = Number(a[i]) + Number(b[i]) + carry;
result = String(sum % 2) + result;
carry = sum >> 1;
}
if (carry === 1) result = "1" + result;
return result;
}2Optimal (two pointers from the right)
O(max(n, m))Each digit of the longer string is processed once, plus one possible extra carry step.O(max(n, m))The builder holds the result, at most one digit longer than the longer input.Keep one pointer at the end of each string and a carry. While either pointer is still inside its string or a carry remains, add the available digits and the carry, append sum % 2 to a builder, and move both pointers left. The digits come out least significant first, so reverse the builder once at the end.
- Set i = a.length - 1, j = b.length - 1, carry = 0.
- While i >= 0 or j >= 0 or carry > 0: sum = carry plus a[i] (if i >= 0) plus b[j] (if j >= 0).
- Append sum % 2, set carry = sum / 2, and decrement i and j.
- Reverse the builder and return it.
class Solution {
public String addBinary(String a, String b) {
StringBuilder sb = new StringBuilder();
int i = a.length() - 1, j = b.length() - 1, carry = 0;
while (i >= 0 || j >= 0 || carry > 0) {
int sum = carry;
if (i >= 0) sum += a.charAt(i--) - '0';
if (j >= 0) sum += b.charAt(j--) - '0';
sb.append(sum % 2);
carry = sum / 2;
}
return sb.reverse().toString();
}
}class Solution:
def addBinary(self, a: str, b: str) -> str:
out = []
i, j, carry = len(a) - 1, len(b) - 1, 0
while i >= 0 or j >= 0 or carry:
total = carry
if i >= 0:
total += ord(a[i]) - 48
i -= 1
if j >= 0:
total += ord(b[j]) - 48
j -= 1
out.append("1" if total % 2 else "0")
carry = total // 2
return "".join(reversed(out))class Solution {
public:
string addBinary(string a, string b) {
string out;
int i = a.size() - 1, j = b.size() - 1, carry = 0;
while (i >= 0 || j >= 0 || carry > 0) {
int sum = carry;
if (i >= 0) sum += a[i--] - '0';
if (j >= 0) sum += b[j--] - '0';
out.push_back(char('0' + sum % 2));
carry = sum / 2;
}
reverse(out.begin(), out.end());
return out;
}
};function addBinary(a, b) {
const out = [];
let i = a.length - 1, j = b.length - 1, carry = 0;
while (i >= 0 || j >= 0 || carry > 0) {
let sum = carry;
if (i >= 0) sum += a.charCodeAt(i--) - 48;
if (j >= 0) sum += b.charCodeAt(j--) - 48;
out.push(sum % 2);
carry = sum >> 1;
}
return out.reverse().join("");
}Edge cases to test
- A final carry that makes the result one digit longer than both inputs
- Inputs of very different lengths
- One or both inputs equal to "0"
- Strings far too long to fit in any built-in integer type
Hints
Hint 1
Add the numbers the way you would by hand: start from the last digit of each string and move left.
Hint 2
At each position the sum is digitA + digitB + carry, which is between 0 and 3. The digit you write is sum % 2 and the new carry is sum / 2.
Hint 3
Appending digits and reversing once at the end is cheaper than putting each new digit at the front of a string.
FAQ
What is the best time complexity for Add Binary?
Optimal (two pointers from the right) runs in O(max(n, m)) time and O(max(n, m)) extra space. Each digit of the longer string is processed once, plus one possible extra carry step.
Which pattern does Add Binary use?
It is a arrays & hashing problem that uses the right to left traversal pattern. Other problems with the same pattern: Array Leaders, Product of Array Except Self, Next Permutation.
Is there a brute force solution for Add Binary?
Yes. Brute force (pad and prepend) takes O(n²) time and O(n) space. Pad the shorter string with leading zeros so both have the same length, then add column by column from the right.
Which edge cases should I test for Add Binary?
A final carry that makes the result one digit longer than both inputs; Inputs of very different lengths; One or both inputs equal to "0"; Strings far too long to fit in any built-in integer type.