Any more efficient method for Add Binary?


  • -10
    E

    The following is my solution for this problem. Actually, it takes me much time to get through this perfectly. I want to know are there any other better solution for this problem? If anyone has a better and more efficient and less complicated method, please share with us.

    public static String addBinary(String a, String b) {
    	long sum = 0;
    	String resultString = "";
    	List<String> aStrings = new LinkedList<String>();
    	List<String> bStrings = new LinkedList<String>();
    	int len_a = a.length();
    	int i = len_a;
    	int carry = 0;
    	while (i - 16 > 0) {
    		aStrings.add(a.substring(i - 16, i));
    		i = i - 16;
    	}
    	aStrings.add(a.substring(0, i));
    	
    	int len_b = b.length();
    	i = len_b;
    	while (i - 16 > 0) {
    		bStrings.add(b.substring(i - 16, i));
    		i = i - 16;
    	}
    	bStrings.add(b.substring(0, i));
    	int index = 0;
                
    	while (index < Math.min(aStrings.size(), bStrings.size())) {
    		long binary_a = stringToInteger(aStrings.get(index));
    		long binary_b = stringToInteger(bStrings.get(index));
    		sum = binary_a + binary_b + carry;
    		String tempString = binaryToString(sum);
    		if (tempString.length() > 16) {
    			carry = 1;
    			tempString = tempString.substring(1);
    			resultString = tempString + resultString;
    		} else {
    			carry = 0;
    			if (index < Math.max(bStrings.size()-1,aStrings.size()-1)) {
    				while (tempString.length() < 16) {
    					tempString = "0" + tempString;
    				}
    			}
    			resultString = tempString + resultString;
    		}
    		index++;
    	}
               //add the rest of a string
    	while (index < aStrings.size()) {
    		long binary_a = stringToInteger(aStrings.get(index));
    		long binary_b = 0;
    		sum = binary_a + binary_b + carry;
    		String tempString = binaryToString(sum);
    		if (tempString.length() > 16) {
    			carry = 1;
    			tempString = tempString.substring(1);
    			resultString = tempString + resultString;
    		} else {
    			carry = 0;
    			if (index != aStrings.size()-1 ) {
    				while (tempString.length() < 16) {
    					tempString = "0" + tempString;
    				}
    			}
    			resultString = tempString + resultString;
    		}
    		index++;
    	}
                // add the rest of b string
    	while (index < bStrings.size()) {
    		long binary_a = 0;
    		long binary_b = stringToInteger(bStrings.get(index));
    		sum = binary_a + binary_b + carry;
    		String tempString = binaryToString(sum);
    		if (tempString.length() > 16) {
    			carry = 1;
    			tempString = tempString.substring(1);
    			resultString = tempString + resultString;
    		} else {
    			carry = 0;
    			if (index != bStrings.size()-1) {
    				while (tempString.length() < 16) {
    					tempString = "0" + tempString;
    				}
    			}
    			resultString = tempString + resultString;
    		}
    		index++;
    	}
    	//add the last carry
    	if(carry==1){
    		resultString="1"+resultString;
    	}
    
    	return resultString;
    }
    
    public static long stringToInteger(String s) {
    	if (s == "") {
    		return 0;
    	}
    	int result = 0;
    	int len = s.length();
    	if (s.equals("0")) {
    		return 0;
    	}
    	for (int i = 0; i < len; i++) {
    		if (s.charAt(len - 1 - i) == '1') {
    			result += Math.pow(2, i);
    
    		}
    	}
    	return result;
    }
    
    public static String binaryToString(long num) {
    	String result = "";
    	long temp = num;
    	int maxPow = 0;
    	int sum = 0;
    	while (Math.pow(2, maxPow) <= temp) {
    		maxPow++;
    	}
    	if (maxPow != 0) {
    		maxPow--;
    	}
    	for (int pow = maxPow; pow >= 0; pow--) {
    
    		if ((sum + Math.pow(2, pow)) <= temp) {
    			sum += Math.pow(2, pow);
    			result = result + "1";
    		} else {
    			result = result + "0";
    		}
    	}
    	return result;
    }

  • 1
    W

    No need extract space with linklist
    the c code show as

    string addBinary(string a, string b) {
    int aLength = a.size();
    int bLength = b.size();
    size_t maxLength = max(aLength, bLength);
    string result;
    result.reserve(maxLength + 1);
    int carrier = 0;
    char ch;
    int xst;
    while (aLength && bLength) {
        xst = carrier + a[--aLength]
        + b[--bLength] - 0x60;
        carrier = xst>>1;
        ch = (xst&0x1) + 0x30;
        result.push_back(ch);
    }
    while (aLength > 0) {
        xst = carrier + a[--aLength] - 0x30;
        carrier = xst>>1;
        ch = (xst&0x1) + 0x30;
        result.push_back(ch);
    }
    while (bLength > 0) {
        xst = carrier + b[--bLength] - 0x30;
        carrier = xst>>1;
        ch = (xst&0x1) + 0x30;
        result.push_back(ch);
    }
    if (carrier) {
        result.push_back('1');
    }
    reverse(result.begin(), result.end());
    return result;
    }

  • 0
    F

    here's JAVA solution, without using linked list. The idea is simple and straightforward. when adding two binary digits, if both are 1 memorize 1 and drop down 0. if memorized element is 1, and both elements are 1, drop down 1, memorize one. Otherwise drop down the number and memorized elements is 0. ctoi is additional function to convert char into int.

    public class Solution 
    {
        int ctoi(char c)
    	{
    		switch(c)
    		{
    			case '0': return 0;
    			case '1': return 1;
    			default: return -1;
    		}
    	}
        String add(String s1, String s2)
    	{
    		StringBuffer sb1 = new StringBuffer(s1);
    		StringBuffer sb2 = new StringBuffer(s2);
    		StringBuffer sb3 = new StringBuffer();
    		while (sb1.length() != sb2.length())
    		{
    			if (sb1.length()<sb2.length())
    				sb1.insert(0,"0");
    			else
    				sb2.insert(0,"0");
    		}
    		int r=0, size = sb1.length();
    		char c;
    		for (int i=size-1; i>=0; i--)
    		{
    			int sum = ctoi(sb1.charAt(i)) + ctoi(sb2.charAt(i)) + r;
    			if (sum == 3) {c = '1'; r = 1;}
    			else if (sum == 2) {c = '0'; r = 1;}
    			else if (sum == 1) {c = '1'; r = 0;}
    			else if (sum == 0) {c = '0'; r = 0;}
    			else { c = '\0'; r = 0; } //this part is for error handling
    			sb3.insert(0, c);
    		}
    		if (r == 1) sb3.insert(0, "1");
    		
    	 return sb3.toString();
    	}
        public String addBinary(String a, String b)
        {
            return add(a, b);
        }
    }

  • 43

    I also learned this method from other and here's the code and some of my comments

    public String addBinary(String a, String b) {
        int m = a.length();
    	int n = b.length();
    	int carry = 0;
    	String res = "";
        // the final length of the result depends on the bigger length between a and b, 
        // (also the value of carry, if carry = 1, add "1" at the head of result, otherwise)
        int maxLen = Math.max(m, n);
    	for (int i = 0; i < maxLen; i++) {
            // start from last char of a and b
            // notice that left side is int and right side is char
            // so we need to  minus the decimal value of '0'
    		int p = i < m ? a.charAt(m - 1 - i) - '0' : 0;
    		int q = i < n ? b.charAt(n - 1 - i) - '0' : 0;
    		int tmp = p + q + carry;
    		carry = tmp / 2;
    		res = tmp % 2 + res;
    	}
    	return (carry == 0) ? res : "1" + res;
    }

  • -5
    I

    I got a straightforward solution on this, purely char comparison and string concatenation. This is in python.

    class Solution:
    # @param a, a string
    # @param b, a string
    # @return a string
    def addBinary(self, a, b):
    	if a is None or b is None:
    		return None
    	r = ''
    	zero = '0'
    	one = '1'
    	carry = zero		# either 0 or 1
    	i = -1			# index starts from the right
    	while i >= max(len(a), len(b)) * -1 or carry != zero:
    		if i < len(a) * -1:
    			ca = zero
    		else:
    			ca = a[i]
    		if i < len(b) * -1:
    			cb = zero
    		else:
    			cb = b[i]
    		temp = carry + ca + cb 		# a string
    		if temp in ['000']:
    			carry = zero
    			r = zero + r
    		elif temp in ['001', '010', '100']:
    			carry = zero
    			r = one + r
    		elif temp in ['011','101','110']:
    			carry = one
    			r = zero + r
    		else:
    			carry = one
    			r = one + r
    		i -= 1
    	return r

  • 0
    X
    This post is deleted!

  • 2
    X

    Here is a recursive solution in Java:

    public class Solution {
        public String addBinary(String a, String b, int carry) {
            if (a.length()==0 && b.length()==0) {
                if (carry==1) {
                    return "1";
                }
                else {
                    return "";
                }
            }
            String aLeft = a;
            int sum = 0;
            if (a.length()>0){
                aLeft = a.substring(0, a.length()-1);
                sum = sum + a.charAt(a.length()-1) - '0';
            }
            String bLeft = b;
            if (b.length()>0){
                bLeft = b.substring(0, b.length()-1);
                sum = sum + b.charAt(b.length()-1) - '0';
            }
            sum = sum + carry;
            return addBinary(aLeft, bLeft, sum/2) + Integer.toString(sum%2);
            
        }
        public String addBinary(String a, String b) {
            return addBinary(a, b, 0);
        }
    }   

  • 0
    P
    public String addBinary(String a, String b) {
    	char[] res = new char[Math.max(a.length(), b.length()) + 1];
    	res[0] = '0';
    	char[] aCharArray = a.toCharArray();
    	char[] bCharArray = b.toCharArray();
    	for (int carry = 0, i = a.length() - 1, j = b.length() - 1, k = res.length - 1; i >= 0
    			|| j >= 0 || carry > 0; i--, j--, k--) {
    		int x = i >= 0 ? aCharArray[i] - '0' : 0;
    		int y = j >= 0 ? bCharArray[j] - '0' : 0;
    		int sum = carry + x + y;
    		carry = sum > 1 ? 1 : 0;
    		res[k] = (char) (sum % 2 + '0');
    	}
    	// if the first element is '0', we need to get rid of it
    	int offset = '1' - res[0];
    	return new String(res, offset, res.length - offset);
    }

  • 0
    W

    Probably less efficient but simple 1 line Python answer:

    return str(bin(int(a, 2) + int(b, 2)))[2:]

  • -5
    Q

    I'm surprised nobody suggested the obvious Java solution. Simply import BigInteger and let it do the job:

    import java.math.BigInteger;
    public class Solution {
        public String addBinary(String a, String b) {
            return new BigInteger(a, 2).add(new BigInteger(b, 2)).toString(2);
        }
    }

  • 0
    S

    Similar to @zihan's, while it's in Python.

    class Solution:
        # @param a, a string
        # @param b, a string
        # @return a string
        def addBinary(self, a, b):
            if not a or not b:
                return a or b
            
            index = -1
            carry = 0
            result = []
            while -index <= max(len(a), len(b)):
                x = int(a[index]) if -index <= len(a) else 0
                y = int(b[index]) if -index <= len(b) else 0
                carry, remainder = divmod(x + y + carry, 2)
                result.append(remainder)
                index -= 1
            
            if carry:
                result.append(carry)
            
            return ''.join(map(str, reversed(result)))

  • 0
    X
    class Solution:
        # @param a, a string
        # @param b, a string
        # @return a string
        def addBinary(self,a,b):
            reslen = max(len(a),len(b))
            a,b=a.rjust(reslen,'0')[::-1],b.rjust(reslen,'0')[::-1]
            carry,res=0,''
            for i in range(reslen):
                carry,num=divmod(int(a[i])+int(b[i])+carry,2)
                res+=str(num)
            if carry:
                res+='1'
            return res[::-1]
    

  • 0
    A
    This post is deleted!

  • 0
    S
    This post is deleted!

  • 6
    G

    zihan's solution can ping simplified as:

    public class Solution {
    public String addBinary(String a, String b) {
        String result = "";
        int m = a.length();
        int n = b.length();
    
        int tmp = 0;
    
        while (m+n >0){
            tmp += m>0? a.charAt(--m) - '0': 0;
            tmp += n>0? b.charAt(--n) - '0': 0;
            
            result = tmp%2 +result;
            tmp /= 2;
        }
        return (tmp == 0)? result: "1"+result;
    }
    

    }


  • 0
    L

    Haha I was using the same method!


  • 0
    L
    This post is deleted!

  • 0
    S

    what if one of the given binary string is negative?


  • 0
    S

    Thanks for your post. However it would be better to share solution with correct code format and elaborated thoughts. Please read the Discuss FAQ for more info. Take a look at good sharing example


  • 0
    T

    my code:

    public String addBinary(String a, String b) {
    	int lenth = a.length() > b.length() ? a.length() + 1 : b.length() + 1;
    	char[] ac = toChar(a, lenth);
    	char[] bc = toChar(b, lenth);
    	int[] sum = new int[lenth];
    	for (int i = 0; i < ac.length; i++) {
    		sum[i] = ((ac[i] - '0') + (bc[i] - '0'));
    	}
    	for (int i = sum.length - 1; i >= 0; i--) {
    		if (sum[i] >= 2) {
    			sum[i] %= 2;
    			sum[i - 1] += 1;
    		}
    	}
    	StringBuffer sb = new StringBuffer();
    	boolean isZero = true;
    	for (int i = 0; i < sum.length; i++) {
    		if (sum[i] != 0)
    			isZero = false;
    		if (!isZero)
    			sb.append(sum[i]);
    	}
    	if (sb.toString().equals(""))
    		return "0";
    	return sb.toString();
    }
    
    private char[] toChar(String a, int lenth) {
    	char[] ac = new char[lenth];
    	int j = 0;
    	for (; j < lenth - a.length(); j++) {
    		ac[j] = '0';
    	}
    	for (; j < ac.length; j++) {
    		ac[j] = a.charAt(j - (lenth - a.length()));
    	}
    	return ac;
    }

Log in to reply
 

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