67. Add Binary

January 10, 2022

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.

code

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

code wrong ans,

class Solution {
  public String addBinary(String a, String b) {
    return Integer.toBinaryString(Integer.parseInt(a, 2) + Integer.parseInt(b, 2));
  }
}

this approach is limited by the length of the input strings a and b. Once the string is long enough, the result of conversion into integers will not fit into Integer, Long or BigInteger: 33 1-bits - and b doesn’t fit into Integer. 65 1-bits - and b doesn’t fit into Long. 500000001 1-bits - and b doesn’t fit into BigInteger

code

import java.math.BigInteger;
class Solution {
  public String addBinary(String a, String b) {
    BigInteger x = new BigInteger(a, 2);
    BigInteger y = new BigInteger(b, 2);
    BigInteger zero = new BigInteger("0", 2);
    BigInteger carry, answer;
    while (y.compareTo(zero) != 0) {
      answer = x.xor(y);
      carry = x.and(y).shiftLeft(1);
      x = answer;
      y = carry;
    }
    return x.toString(2);
  }
}

code

class Solution:
    def addBinary(self, a, b) -> str:
        x, y = int(a, 2), int(b, 2)
        while y:
            x, y = x ^ y, (x & y) << 1
        return bin(x)[2:]