LeetCode Add Binary: Math Simulation with String

Overview

LeetCode Add Binary: This is a Math Simulation with String, the solution and precautions are given as well as the detailed algorithm ideas and analysis.

LeetCode Add Binary

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

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

Solution: Math Simulation with String

Just simulate the process of regular binary addition: start from the least significant digits and calculate both the carry and the value on the corresponding position of the result. The following Java code is accepted by LeetCode OJ to pass this Add Binary problem:

public class Solution {
    public String addBinary(String a, String b) {
        StringBuffer stringBuffer = new StringBuffer();

        int carry = 0;
        int sum = 0;

        int i = a.length() - 1;
        int j = b.length() - 1;
        int aa = 0, bb = 0;

        while (i >= 0 || j >= 0) {
            aa = (i >= 0) ? Character.getNumericValue(a.charAt(i)) : 0;
            bb = (j >= 0) ? Character.getNumericValue(b.charAt(j)) : 0;
            sum = carry + aa + bb;
            carry = sum / 2;
            sum %= 2;
            stringBuffer.append(sum);
            --i; --j;
        }
        if (carry > 0)
            stringBuffer.append(carry);
        return stringBuffer.reverse().toString();
    }
}

Remarks:

(1) The length of the two input strings might not be the same, don’t forget to process the leftover digits and there could be multiple leftover digits so make sure to use something like a while loop rather than just a single if statement to process ALL the leftoevers.

(2) Don’t forget the last carry, for example, a = “111″ b  = “1″, then the result consists of FOUR digits including the last carry 1.

Summary

LeetCode Add Binary: This is a Math Simulation with String, the solution and precautions are given as well as the detailed algorithm ideas and analysis.

Written on January 9, 2013