# Simple accepted java 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;
}
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.

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

}
``````

}

• the usage of XOR is fantastic!

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

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

• Very Nice！Good Job！

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

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

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

• very nice!! great job

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

Anyone know how to fix this?

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

• 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)."

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

}

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

• 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,
reduce the likelihood of error. "

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

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

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

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

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