# Question

Formatted question description: https://leetcode.ca/all/67.html

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.

# Algorithm

When adding two binary strings, it’s important to consider potential carries that can affect subsequent additions. Additionally, the input strings may not have the same length. To address this, we can create a new string with a length equal to the larger of the two input strings, and prepend the shorter string with ‘0’s to match this length.

To add the two strings, we start from the end of each string and work our way towards the beginning. We take the binary value of each character (0 or 1) and add them together. If the sum is less than 2, we append this sum to our result string. If the sum is equal to or greater than 2, we add a ‘0’ to the result string and set the carry flag to 1.

Once we have iterated through all characters in both input strings, we check if there is still a carry flag. If there is, we append a ‘1’ to our result string. Finally, we reverse the result string to get the correct binary string sum.

# Code

• import java.math.BigInteger;

public class Solution {
public String addBinary(String a, String b) {

if (a == null || b == null || a.length() == 0 || b.length() == 0) {
return "";
}

// swap to a is longer than b
if (a.length() < b.length()) {
}

String result = "";
int carry = 0;

int i = a.length() - 1; // pointer of string a
int j = b.length() - 1; // pointer of string b

while (j >= 0 || i >= 0) {
add = (a.charAt(i) - '0') + (j < 0? 0 : (b.charAt(j) - '0')) + carry;

} else {
carry = 0;
}

i--;
j--;
}

// final check
if (carry > 0) {
result = carry + result;
}

return result;
}
}

public class Solution_BigInteger { // actually, still possible overflow, just passed OJ test cases
public String addBinary(String a, String b) {
if (a == null || b == null)
return "";
if (a.length() == 0)
return b;
if (b.length() == 0)
return a;

// easily overflow
// int a = Integer.parseInt(a);

BigInteger aa = new BigInteger(a, 2);
BigInteger bb = new BigInteger(b, 2);

}
}

}

############

class Solution {
public String addBinary(String a, String b) {
StringBuilder sb = new StringBuilder();
for (int i = a.length() - 1, j = b.length() - 1, 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();
}
}

• // OJ: https://leetcode.com/problems/add-binary/
// Time: O(A+B)
// Space: O(1)
class Solution {
public:
string addBinary(string a, string b) {
int i = a.size() - 1, j = b.size() - 1, carry = 0;
string ans;
while (i >= 0 || j >= 0 || carry) {
if (i >= 0) carry += a[i--] - '0';
if (j >= 0) carry += b[j--] - '0';
ans += '0' + (carry & 1);
carry >>= 1;
}
return string(rbegin(ans), rend(ans));
}
};

• class Solution:
def addBinary(self, a: str, b: str) -> str:
return bin(int(a, 2) + int(b, 2))[2:]

############

class Solution(object):
"""
:type a: str
:type b: str
:rtype: str
"""
diff = abs(len(a) - len(b))
if len(a) > len(b):
b = "0" * diff + b
else:
a = "0" * diff + a

ret = ""
carry = 0
ai, bi = len(a) - 1, len(b) - 1
al, bl = len(a), len(b)
while ai >= 0 and bi >= 0:
ac, bc = a[ai], b[bi]
if ac == "1" and bc == "1":
if carry == 1:
ret += "1"
else:
ret += "0"
carry = 1
elif ac == "0" and bc == "0":
if carry == 1:
ret += "1"
else:
ret += "0"
carry = 0
else:
if carry == 1:
ret += "0"
else:
ret += "1"

ai -= 1
bi -= 1

if carry == 1:
ret += "1"
return ret[::-1]


• func addBinary(a string, b string) string {
for len(a) > len(b) {
b = "0" + b
}
for len(a) < len(b) {
a = "0" + a
}
zero := []byte("0")[0]
ret := make([]byte, len(a))
for right := len(a) - 1; right > 0; right-- {
t := ret[right] + a[right] + b[right] - zero*2
ret[right] = t%2 + zero
if t >= 2 {
ret[right-1] = 1
}
}
t := ret[0] + a[0] + b[0] - zero*2
ret[0] = t%2 + zero
if t >= 2 {
ret = append([]byte("1"), ret...)
}

return string(ret)
}


• function addBinary(a: string, b: string): string {
const n = Math.max(a.length, b.length);
const res = [];
let isOver = false;
for (let i = 0; i < n || isOver; i++) {
let val = isOver ? 1 : 0;
isOver = false;
if (a[a.length - i - 1] === '1') {
val++;
}
if (b[b.length - i - 1] === '1') {
val++;
}
if (val > 1) {
isOver = true;
val -= 2;
}
res.push(val);
}
return res.reverse().join('');
}


• using System;
using System.Collections.Generic;

public class Solution {
public string AddBinary(string a, string b) {
var list = new List<char>(Math.Max(a.Length, b.Length) + 1);
var i = a.Length - 1;
var j = b.Length - 1;
var carry = 0;
while (i >= 0 || j >= 0)
{
if (i >= 0)
{
carry += a[i] - '0';
}
if (j >= 0)
{
carry += b[j] - '0';
}
carry /= 2;
--i;
--j;
}
if (carry > 0) list.Add((char) (carry + '0'));
list.Reverse();
return new string(list.ToArray());
}
}

• impl Solution {
pub fn add_binary(a: String, b: String) -> String {
let n = a.len().max(b.len());
let (a, b) = (a.as_bytes(), b.as_bytes());
let mut res = vec![];
let mut is_over = false;
let mut i = 0;
while i < n || is_over {
let mut val = if is_over { 1 } else { 0 };
is_over = false;
if a.get(a.len() - i - 1).unwrap_or(&b'0') == &b'1' {
val += 1;
}
if b.get(b.len() - i - 1).unwrap_or(&b'0') == &b'1' {
val += 1;
}
if val > 1 {
is_over = true;
val -= 2;
}
i += 1;
res.push(char::from(b'0' + val));
}
res.iter().rev().collect()
}
}