Question

Formatted question description: https://leetcode.ca/all/67.html

67	Add Binary

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

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

Algorithm

When adding each bit, there may be a carry, which will affect the result of the subsequent addition. And the length of the two input strings may also be different. At this time, we need to create a new string, whose length is the larger of the two input strings, and add the character ‘0’ to the beginning of the shorter input string to fill the larger length. At this time, the characters are taken out from the end of the two strings one by one, and then converted into numbers, and added. If it is greater than or equal to 2, mark the carry flag carry, and add a character ‘0’ to the new string.

Code

Java

import java.math.BigInteger;

public class Add_Binary {

	public class Solution {
	    public String addBinary(String a, String b) {

	        if (a == null || b == null || a.length() == 0 || b.length() == 0) {
	            return "";
	        }

	        // swap to a is longer than b
	        if (a.length() < b.length()) {
	            return addBinary(b, a);
	        }

	        String result = "";
	        int carry = 0;
	        int add = -1; // each position add up

	        int i = a.length() - 1; // pointer of string a
	        int j = b.length() - 1; // pointer of string b

	        while (j >= 0 || i >= 0) {
	            add = (a.charAt(i) - '0') + (j < 0? 0 : (b.charAt(j) - '0')) + carry;

	            if (add >= 2) {
	                carry = add / 2;
	                add = add % 2;
	            } else {
	                carry = 0;
	            }

	            result = add + result;

	            i--;
	            j--;
	        }

	        // final check
	        if (carry > 0) {
	            result = carry + result;
	        }

	        return result;
	    }
	}

	public class Solution_BigInteger { // actually, still possible overflow, just passed OJ test cases
		public String addBinary(String a, String b) {
			if (a == null || b == null)
				return "";
			if (a.length() == 0)
				return b;
			if (b.length() == 0)
				return a;

			// easily overflow
			// int a = Integer.parseInt(a);

			BigInteger aa = new BigInteger(a, 2);
			BigInteger bb = new BigInteger(b, 2);

			BigInteger add = aa.add(bb);

			return add.toString(2);
		}
	}

}

All Problems

All Solutions