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 <= 10⁴
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 Add_Binary {

	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()) {
	            return addBinary(b, a);
	        }

	        String result = "";
	        int carry = 0;
	        int add = -1; // each position add up

	        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;

	            if (add >= 2) {
	                carry = add / 2;
	                add = add % 2;
	            } else {
	                carry = 0;
	            }

	            result = add + result;

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

			BigInteger add = aa.add(bb);

			return add.toString(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):
  def addBinary(self, a, b):
    """
    :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';
            }
            list.Add((char)((carry % 2) + '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()
    }
}

67 - Add Binary

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions