Short AC solution in Java with explanation


  • 157
    L
    public class Solution {
        public String addBinary(String a, String b) {
            StringBuilder sb = new StringBuilder();
            int i = a.length() - 1, j = b.length() -1, carry = 0;
            while (i >= 0 || j >= 0) {
                int sum = carry;
                if (j >= 0) sum += b.charAt(j--) - '0';
                if (i >= 0) sum += a.charAt(i--) - '0';
                sb.append(sum % 2);
                carry = sum / 2;
            }
            if (carry != 0) sb.append(carry);
            return sb.reverse().toString();
        }
    }
    

    Computation from string usually can be simplified by using a carry as such.


  • 19
    S

    Same idea with bitwise operation.

    public String addBinary(String a, String b) {
        int i = a.length() - 1;
        int j = b.length() - 1;
        int carry = 0;
        StringBuilder sb = new StringBuilder();
        
        while (i >= 0 || j >= 0 || carry > 0){
            int sum = ((i < 0) ? 0 : (a.charAt(i--) - '0')) + 
                        ((j < 0) ? 0 : (b.charAt(j--) - '0')) + 
                        carry; 
            
            sb.append(Integer.toString(sum & 1));
            carry = (sum >> 1) & 1;
        }
        
        return sb.reverse().toString();
    }
    

  • 21

    niubility!!!!!


  • 0
    D

    @song4you very concise and straightforward solution, learned a lot, thanks!


  • 0

    Should we consider the case that String with leading "0"s?
    Test of "0001" + "1" failed.
    Should return "10" but "0010".
    Though this kind of test cases is not included in tests.


  • -1
    This post is deleted!

  • 3

    @zz7.tiannan You are right in terms of saving code amount. But using insert every time may actually cost more time compared to first appending and then reversing at the end, since the implementation of StringBuilder is array instead of linkedlist http://stackoverflow.com/questions/26170180/complexity-of-insert0-c-operation-on-stringbuffer-is-it-o1
    So it may still be better to use append and reverse method.


  • 0

    How could you finally get this solution... Awesome ,man.


  • 0

    @OpMaker Got it.I didn't concern the time complexity of insert().hhh


  • 1
    F

    Only use char array beats 86%.

        public String addBinary(String a, String b) {
            int alength = a.length();
            int blength = b.length();
            int length = alength > blength ? (alength+1) : (blength+1);
            char[] sb = new char[length];
            int count = 1;
            boolean hasCarry = false;
            for (int i = 0; i < length; i ++) {
                int aIndex = alength - 1 - i;
                int bIndex = blength - 1 - i;
                int aNum = (aIndex >= 0 && aIndex < alength) ? (a.charAt(aIndex) - '0') : 0;
                int bNum = (bIndex >= 0 && bIndex < blength) ? (b.charAt(bIndex) - '0') : 0;
                int current = aNum + bNum + (hasCarry ? 1 : 0);
                sb[length - i - 1] = (char)(current % 2 + '0');
                hasCarry = (current > 1);
                if (i >= alength - 1 && i >= blength - 1 && !hasCarry) {
                    break;
                }
                count ++;
            }
            return String.valueOf(sb, length - count, count);
        }
    

  • 0

    The solution is very clear and straightforward! Bravo, guys..


  • 1
    M

    @lx223 Hi, could you please explain 'sum += s1.charAt(first) - '0';' but to me please. Thanks


  • 0

    nice solution


  • 5
    Q

    @mohul when we have a char that represents a ASCII/unicode digit, and the smallest possible ASCII/unicode digit is substracted, then value corresponding to the digit would be left. Thus, here, when we get char from s1.charAt(first), subtract it from '0' can help us get the corresponding value to the digit.


  • 0
    C

    @lx223 You said string computation can be dealt with carry. But I didn't understand why we use carry and what it is for? Thanks


  • 0
    W

    Hey I just want to confirm, is the time complexity O(n + m)?
    where n is length of first string and
    m is length of second?


  • 0
    S

    @Wondergirl46 I guess the time complexity of O(Max(n,m));


  • 0

    that's a really good idea! thanks


  • 0
    J

    Same solution here.

    public class Solution {
        public String addBinary(String a, String b) {
            if (a.length()==0 && b.length()==0) {return "0";}
            char[] arrA = a.toCharArray();
            char[] arrB = b.toCharArray();
            
            int carry = 0;
            int i = arrA.length-1;
            int j = arrB.length-1;
            StringBuilder sb = new StringBuilder();
            
            while (carry!=0 || i>=0 || j>=0) {
                if (i>=0) { carry += (arrA[i]-'0');}
                if (j>=0) { carry += (arrB[j]-'0');}
                int digit = carry%2;
                carry = carry>>1;
                sb.append(digit);
                i--;
                j--;
            }
            
            return sb.reverse().toString();
        }
    }
    

  • 2
    C

    Just want to share, without carry variable, thanks !

     public String addBinary(String a, String b) {
            StringBuilder sb = new StringBuilder();
            int i = a.length()-1, j = b.length()-1, sum = 0;
            while(i >= 0 || j >= 0){
                sum = sum / 2; 
                
                if(i >= 0)
                    sum += a.charAt(i--)-'0';
                if(j >= 0)
                    sum += b.charAt(j--)-'0';
        
                sb.append(sum%2);
            }
            if(sum/2 != 0)sb.append(1);
            return sb.reverse().toString();
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.