Simple accepted java solution


  • 68
    M
    public class Solution {
        public String addBinary(String a, String b) {
            if(a == null || a.isEmpty()) {
                return b;
            }
            if(b == null || b.isEmpty()) {
                return a;
            }
            char[] aArray = a.toCharArray();
            char[] bArray = b.toCharArray();
            StringBuilder stb = new StringBuilder();
    
            int i = aArray.length - 1;
            int j = bArray.length - 1;
            int aByte;
            int bByte;
            int carry = 0;
            int result;
    
            while(i > -1 || j > -1 || carry == 1) {
                aByte = (i > -1) ? Character.getNumericValue(aArray[i--]) : 0;
                bByte = (j > -1) ? Character.getNumericValue(bArray[j--]) : 0;
                result = aByte ^ bByte ^ carry;
                carry = ((aByte + bByte + carry) >= 2) ? 1 : 0;
                stb.append(result);
            }
            return stb.reverse().toString();
        }
    }
    

    Addition bits are calculated by xor. Carry bit is calculated as simple integer addition.


  • 0
    Y
    public class Solution {
    public String addBinary(String a, String b) {
        if (a=="" && b=="") return "";
        
        
        int[] sum=new int[Math.max(a.length(), b.length())];
        int flag=0;
        
        int i=1;
        
        while (i<=sum.length){
            int anum=0;
            int bnum=0;
            if (i<=a.length()){
                anum=Character.getNumericValue(a.charAt(a.length()-i));
            }
            if (i<=b.length()){
                bnum=Character.getNumericValue(b.charAt(b.length()-i));
            }
            switch (anum+bnum+flag){
                case 0: 
                    sum[sum.length-i]=0;
                    flag=0;
                    break;
                case 1:
                    sum[sum.length-i]=1;
                    flag=0;
                    break;
                case 2:
                    sum[sum.length-i]=0;
                    flag=1;
                    break;
                    
                case 3:
                    sum[sum.length-i]=1;
                    flag=1;
                    break;
            }
            i++;
            
            
        }
        String r="";
        for (int k=0;k<sum.length;k++){
            r+=Integer.toString(sum[k]);
        }
        
        if (flag==1){
            return "1"+r;
        }
        return r;
        
        
        
    }
    

    }


  • 1
    N

    the usage of XOR is fantastic!


  • 11
    G

    Very nice! here is without using those 2 extra arrays

    public class Solution {
        public String addBinary(String a, String b) {
            if(a == null || a.isEmpty()) 
                return b;
            if(b == null || b.isEmpty()) 
                return a;
        
            
            StringBuilder stb = new StringBuilder();
            int i = a.length() - 1;
            int j = b.length() - 1;
            int aBit;
            int bBit;
            int carry = 0;
            int result;
    
            while(i >= 0 || j >= 0 || carry == 1) {
                aBit = (i >= 0) ? Character.getNumericValue(a.charAt(i--)) : 0;
                bBit = (j >= 0) ? Character.getNumericValue(b.charAt(j--)) : 0;
                result = aBit ^ bBit ^ carry;
                carry = ((aBit + bBit + carry) >= 2) ? 1 : 0;
                stb.append(result);
            }
            return stb.reverse().toString();
        }
    }

  • 1
    R
    public String addBinary(String a, String b) {
    	a = new StringBuilder(a).reverse().toString();
    	b = new StringBuilder(b).reverse().toString();
    	int maxLen = Math.max(a.length(), b.length());
    	StringBuilder res = new StringBuilder(maxLen);
    	int ia, ib, carry = 0;
    	for (int i = 0; i <= maxLen; i++) {
    		ia = (i < a.length() ? Integer.parseInt(a.charAt(i) + "") : 0);
    		ib = (i < b.length() ? Integer.parseInt(b.charAt(i) + "") : 0);
    		int sum = ia + ib + carry;
    		carry = sum >= 2 ? 1 : 0;
    		if (i != maxLen || sum != 0) res.append(sum % 2);
    	}
    	return res.reverse().toString();
    }

  • 0
    O

    Very Nice!Good Job!


  • 0
    M

    full adder logic from digital electronics can be used.. Cin is carry in and Cout is carry out:
    S = A xor B xor Cin
    Cout = AB + Cin(A xor B)
    http://en.wikipedia.org/wiki/Adder_(electronics)


  • 0
    S
    public String addBinary(String a, String b) {
            // ignore validate
            int iALen = a.length();
            int iBLen = b.length();
            int iMaxLen = Math.max(iALen, iBLen);
            String result = "";
            int carry = 0; 
            for (int i = 0; i < iMaxLen; i++) {
                int aChr = iALen - i - 1 < 0 ? 0 : a.charAt(iALen - i - 1) - 48;
                int bChr = iBLen - i - 1 < 0 ? 0 : b.charAt(iBLen - i - 1) - 48;
                int xor = aChr ^ bChr ^ carry;
                result = xor + result;
                carry = ((aChr ^ bChr) & carry) | (aChr & bChr); 
            }
            return carry == 0 ? result : carry + result;
        }

  • 5
    D

    simple and easy to uderstand solution!

    public String addBinary(String a, String b) {
        int len1 = a.length();
        int len2 = b.length();
        if(len1==0 || len2==0)
            return len1==0? b: a;
        int index1 = len1-1;
        int index2 = len2-1;
        int promote = 0;
        StringBuffer str = new StringBuffer();
        while(index1>=0 || index2>=0 || promote==1) {
            int num1 = index1>= 0?  a.charAt(index1)-'0'  :  0;
            int num2 = index2>= 0?  b.charAt(index2)-'0'  :  0;
            int pos = (num1+num2+promote)%2;
            promote = (num1+num2+promote)/2;
            str.insert(0,pos);
            index1--;
            index2--;
        }
        return new String(str);
    }

  • 0
    D

    very nice!! great job


  • 0
    V

    I tested this code. But I got:
    java.lang.OutOfMemoryError: Java heap space
    at java.util.Arrays.copyOf(Arrays.java:2367)
    at java.lang.AbstractStringBuilder.expandCapacity(AbstractStringBuilder.java:130)
    at java.lang.AbstractStringBuilder.ensureCapacityInternal(AbstractStringBuilder.java:114)
    at java.lang.AbstractStringBuilder.append(AbstractStringBuilder.java:612)
    at java.lang.StringBuilder.append(StringBuilder.java:219)
    at Test.addBinary(Test.java:32)

    Anyone know how to fix this?


  • 1

    Why did you tag this as "constant-space"? You create extra arrays and a StringBuilder as long as the inputs.


  • 0
    H

    However, take a look at http://stackoverflow.com/questions/5931261/java-use-stringbuilder-to-insert-at-the-beginning
    "This will turn an O(n²) solution into O(n)."


  • 0
    H

    I tried to combine all best practices (stolen from other answers) in one simple solution.

    public class Solution {
    public String addBinary(String a, String b) {
        if(a == null || a.isEmpty()) 
            return b;
        if(b == null || b.isEmpty()) 
            return a;
        
        StringBuilder s = new StringBuilder();
        
        int i = a.length() - 1;
        int j = b.length() - 1;
        
        int carry = 0;
        
        while( j >= 0 || i >= 0 || carry == 1 ){
            int cA = (i>=0) ? a.charAt(i--) - '0' : 0; // here is i-- to avoid later subtraction
            int cB = (j>=0) ? b.charAt(j--) - '0' : 0;
            int sum = (cA+cB+carry)%2; // == cA ^ cB ^ carry , choose whatever you want :)
            carry = (cA+cB+carry)/2; // better in readability than ((aByte + bByte + carry) >= 2) ? 1 : 0;
            
            s.append(sum);
        }
    
        return s.reverse().toString();
    }
    

    }


  • 0
    S

    It is a very good solution. Can someone explain why the formula for carry A&B doesn't work here just as the formula for SUM ?


  • 0

    Variables should be declared as close to where they are used as possible.

    You should at least keep aByte, bByte and result inside the while loop for better coding style, making RAII easier and optimizer work better.

    From Google code style guidelines - Limit Variable Scope:

    "The scope of local variables should be kept to a minimum. By doing so,
    you increase the readability and maintainability of your code and
    reduce the likelihood of error. "


  • 0

    You should at least keep aByte, bByte, and result inside the while loop for better coding style, making RAII easier and optimizer work better. Variables should be declared as close to where they are used as possible.


  • 3

    A fast & slick version:

    public String addBinary(String a, String b) {
        if(a == null || a.length() == 0) return b;
        if(b == null || b.length() == 0) return a;
            
        StringBuilder builder = new StringBuilder();
        int i = a.length() - 1, j = b.length() - 1, c = 0;
             
        while(i >= 0 || j >= 0 || c == 1) {
            c += i >= 0 ? a.charAt(i --) - '0' : 0;
            c += j >= 0 ? b.charAt(j --) - '0' : 0;
                
            builder.append((char) ('0' + c % 2));
            c = c > 1 ? 1 : 0;
        }
        return builder.reverse().toString();
    }

  • 0
    E

    Short and easy to understand code

    public class Solution {
        public String addBinary(String a, String b) {
            StringBuilder sb = new StringBuilder();
            int carry = 0;
            for (int i = 0; i < Math.max(a.length(), b.length()) || carry != 0; i++) {
                int ia = (i >= a.length()) ? 0 : a.charAt(a.length() - i - 1) - '0';
                int ib = (i >= b.length()) ? 0 : b.charAt(b.length() - i - 1) - '0';
                sb.insert(0, (ia + ib + carry) % 2);
                carry = (ia + ib + carry) / 2;
            }
            return sb.toString();
        }
    }

  • 0
    W

    In fact,the efficiency is lower to use charAt()


Log in to reply
 

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