# Any more efficient method for Add Binary?

• 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 = "";
int len_a = a.length();
int i = len_a;
int carry = 0;
while (i - 16 > 0) {
i = i - 16;
}

int len_b = b.length();
i = len_b;
while (i - 16 > 0) {
i = i - 16;
}
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++;
}
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;
}``````

• 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;
}``````

• 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;
}
}
{
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)
{
}
}``````

• 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;
}``````

• 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
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``````

• This post is deleted!

• 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) {
}
}   ``````

• ``````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);
}``````

• Probably less efficient but simple 1 line Python answer:

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

• 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);
}
}``````

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

``````class Solution:
# @param a, a string
# @param b, a string
# @return a string
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)))``````

• ``````class Solution:
# @param a, a string
# @param b, a string
# @return a string
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]
``````

• This post is deleted!

• This post is deleted!

• 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;
}
``````

}

• Haha I was using the same method!

• This post is deleted!

• what if one of the given binary string is negative?

• 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

• 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;
}``````

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