67. Add Binary

Published on September 4, 2023

Question

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

Easy question but you need to find some pattern here.

For each digit you do the math you will get result number 0, 1, 2, 3.

0 is all digit is 0 and no carry from previous adding;

1 and 2 is some intermediate result ;

3 is Both number from two string is 1 and we have a carry digit.

For a specific digit, the final number is the previous result module 2 and the carry is the previous result divide 2. This is actually the process of decimal turn to binary.

Code

class Solution {
    public String addBinary(String a, String b) {
        String res = "";
        int i = a.length() - 1, j = b.length() - 1; 
        int carry = 0;
        
        while (i >= 0 && j >= 0) {
            int ia = a.charAt(i) - '0';
            int ib = b.charAt(j) - '0';
            int cur = (ia + ib + carry) % 2;
            carry = (ia + ib + carry) / 2;
            res = String.valueOf(cur) + res;
            i--;
            j--;
        }
        while (i < 0 && j >= 0) {
            int ib = b.charAt(j) - '0';
            int cur = (ib + carry) % 2;
            carry = (ib + carry) / 2;
            res = String.valueOf(cur) + res;
            j--;
        } 
        while (j < 0 && i >= 0) {
            int ia = a.charAt(i) - '0';
            int cur = (ia + carry) % 2;
            carry = (ia + carry) / 2;
            res = String.valueOf(cur) + res;
            i--;
        }
        if (carry == 1) {
            res = "1" + res;
        }
        return res;
    }
}