Wednesday, July 23, 2014

Add Binary

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

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

public class Solution {
    //Time: O(n)
    public String addBinary(String a, String b) {
        if (a.length() == 0) {
            return b;
        }
        if (b.length() == 0) {
            return a;
        }
        
        StringBuilder res = new StringBuilder();
        int m = a.length() - 1;
        int n = b.length() - 1;
        int carry = 0;
        while (m >= 0 || n >= 0) {
            if (m >= 0) {
                carry += a.charAt(m) == '1' ? 1 : 0;
                m--;
            }
            if (n >= 0) {
                carry += b.charAt(n) == '1' ? 1 : 0;
                n--;
            }
            res.append(carry % 2);
            carry /= 2;
        }
        if (carry == 1) {
            res.append(1);
        }
        res.reverse();
        return res.toString();
    }
}

No comments:

Post a Comment