My straightforward O(n) time, O(1) space C++ solution (please suggest improvements)

• I basically write "0" for shorter string and explicitly check for 3 possible cases.

``````class Solution {
public:
string addBinary(string a, string b) {
string result;

int i = a.length()-1;
int j = b.length()-1;

string a_i, b_j;
bool carry = false;

while (i>=0 || j>=0){
if (i>=0) {
a_i = a[i];
} else {
a_i = "0";
}
if (j>=0){
b_j = b[j];
} else {
b_j = "0";
}

if (a_i == "0" && b_j == "0"){
result = (carry? "1" : "0") + result;
carry  = false;
} else if (a_i == "1" && b_j == "1"){
result = (carry? "1" : "0") + result;
carry = true;
} else {
result = (carry? "0" : "1") + result;
//carry = (carry? true : false);
}
i--;
j--;
}

return (carry? "1" + result : result);
}
};``````

• Exactly to remove extra IFs from the loop I decided to swap the strings and add shorter one to longer one.
Here is my code with comments.

``````class Solution {
public:
string addBinary(string a, string b) {

int l=a.length()-1;  // l stands for Large
int s=b.length()-1;  // s stands for Small

// swap a with b if b is longer, to simplify the logic
if(l<s){
swap(a,b); // swap the strings
l = l^s;        // swap the indexes
s = l^s;
l = l^s;
}

// add one more position in front to reduce extra if in the loop
a.insert(0,1,'0');
l++;

while(s >= 0){

if(b[s]=='1'){
int i=l;
while(a[i]=='1'){
a[i]='0';
i--;
}
a[i]='1';
}

s--;
l--;
}

// remove extra item if it was not necessary
if(a[0]=='0') a.erase(0,1);

return a;
}
};``````

• ``````string addBinary(string a, string b) {
string::reverse_iterator aiter = a.rbegin(), biter = b.rbegin();
for (; aiter != a.rend() && biter != b.rend(); ++aiter, ++biter)
{
if (*aiter == '1' && *biter == '1')
*aiter = '2';
else if (*aiter == '0' && *biter == '1')
*aiter = '1';
}
a = string(b.begin(), b.begin() + (b.rend() - biter)) + a;
char count = '0';
for (aiter = a.rbegin(); aiter != a.rend(); ++aiter)
{
if (*aiter == '2')
{
if (count == '1')
*aiter = '1';
else
*aiter = '0';
count = '1';
}
else if (*aiter == '1')
{
if (count == '1')
*aiter = '0';
}
else
{
*aiter = count;
count = '0';
}
}
if (count != '0')
a = "1" + a;
return a;
}``````

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