Leetcode: Add Binary

Given two binary strings, return their sum (also a binary string).

For example,
a = "11"
b = "1"
Return "100".

Understand the problem:
The problem is quite easy to understand. It add two binary numbers and return their sum as a string as well. The crux to solve the problem is you cannot convert the string to binary numbers and add them up, then convert back to binary. The major reason is the overflow problem. 

Solution:
We can scan the two strings from the end in reverse order. The only thing to note is the carry number. 

Code (Java):

public class Solution {
    public String addBinary(String a, String b) {
        if (a == null || a.length() == 0) {
            return b;
        }
        
        if (b == null || b.length() == 0) {
            return a;
        }
        
        int i = a.length() - 1;
        int j = b.length() - 1;
        int carry = 0;
        
        StringBuilder sb = new StringBuilder();
        
        while (i >= 0 || j >= 0) {
            if (i >= 0) {
                carry += a.charAt(i) - '0';
                i--;
            }
            
            if (j >= 0) {
                carry += b.charAt(j) - '0';
                j--;
            }
            
            sb.insert(0, carry % 2);
            carry /= 2;
        }
        
        if (carry == 1) {
            sb.insert(0, 1);
        }
        
        return sb.toString();
    }
}

Discussion:
The problem itself is very easy. The major concern is the insertion at the head, which may take O(n) time. An alternative solution is to append at the tail, i.e, construct the result in reverse order, and then reverse at least. Since reversing at end only takes O(n) time,  the overall time complexity is still O(n). 

Code (Java):

public class Solution {
    public String addBinary(String a, String b) {
        if (a == null || a.length() == 0) {
            return b;
        }
        
        if (b == null || b.length() == 0) {
            return a;
        }
        
        int i = a.length() - 1;
        int j = b.length() - 1;
        int carry = 0;
        
        StringBuilder sb = new StringBuilder();
        
        while (i >= 0 || j >= 0) {
            if (i >= 0) {
                carry += a.charAt(i) - '0';
                i--;
            }
            
            if (j >= 0) {
                carry += b.charAt(j) - '0';
                j--;
            }
            
            sb.append(carry % 2);
            carry /= 2;
        }
        
        if (carry == 1) {
            sb.append(1);
        }
        
        return sb.reverse().toString();
    }
}

Summary:
The problem itself is very easy. Several take-away messages:
1. Iterate from the end.
2. Don't forget the last carry number after iterations.
3. Try not convert the string to numbers due to the possible overflow matters.