Leetcode–Add Binary

The Problem:

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

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

 

Notes:

  1. Similar to Add Two Numbers, implement a adder with carry so does not matter if binary or hex or decimal.
  2. Be careful don’t forget the last carry when all nodes traversed, should add one more node for carry.

Java Solution:

public class Solution {
    public String addBinary(String a, String b) {
        int lena = a.length();
        int lenb = b.length();
        int len = Math.max(lena, lenb)+1;
        char[] res = new char[len];
        int i = 1;
        int carry = 0;
        while(i<=lena && i <= lenb){
            char ach = a.charAt(lena-i);
            char bch = b.charAt(lenb-i);
            int sum =  (ach-'0')+(bch-'0')+carry;
            res[len-i] =(char)(sum%2 + '0');
            carry = sum/2;
            i++;
        }
        while(i <= lena){
            char ach = a.charAt(lena-i);
            int sum =  (ach-'0')+carry;
            res[len-i] =(char)(sum%2 + '0');
            carry = sum/2;
            i++;

        }
        while(i <= lenb){
            char bch = b.charAt(lenb-i);
            int sum =  (bch-'0')+carry;
            res[len-i] =(char)(sum%2 + '0');
            carry = sum/2;
            i++;

        }
        if(carry!= 0){
            res[len-i] = '1';
            return new String(res);
        }
        else{
            return new String(res).substring(1);
        }
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s