2014年11月29日星期六

[Leetcode] Add Binary

Given two binary strings, return their sum (also a binary string).
For example,
a = "11"
b = "1"
Return "100".

Similar to the problem Plus One. Time complexity is O(n) and we ignore the required return value the space complexity is O(1).


    public String addBinary(String a, String b) {
        if(a.length() < b.length()) {
            return addBinary(b, a);
        }
        StringBuffer sb = new StringBuffer();
        int ind1 = a.length() - 1, ind2 = b.length() - 1;
        int carry = 0;
        while(ind2 >= 0) {
            int num1 = a.charAt(ind1) - '0';
            int num2 = b.charAt(ind2) - '0';
            int res = num1 + num2 + carry;
            carry = res / 2;
            res = res % 2;
            ind1--; ind2--;
            sb.append(res);
        }
        while(ind1 >= 0) {
            int num1 = a.charAt(ind1) - '0';
            int res = num1 + carry;
            carry = res / 2;
            res = res % 2;
            ind1--;
            sb.append(res);
        }
        if(carry != 0)
            sb.append(carry);
        sb = sb.reverse();
        return sb.toString();
    }

没有评论:

发表评论