class Solution {
public:
string addBinary(string a, string b) {
int carry = 0;
string ans = a.size() > b.size() ? a : b;
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
for (int i = 0; i < max((int)a.size(), (int)b.size()); i++) {
int x = i < a.size() ? a[i]  '0' : 0;
int y = i < b.size() ? b[i]  '0' : 0;
ans[i] = (x ^ y) ^ carry + '0';
carry = (x & y)  (carry & (x ^ y));
}
if (carry)
ans += "1";
reverse(ans.begin(), ans.end());
return ans;
}
};
Share my C++ concise solution


Thanks for the approach.
We can use reverse function just once and compare string values from the end as follows.
This approach can save us some valuable execution time (P.S. There is no time difference in leetcode).class Solution { public: string addBinary(string a, string b) { string output ; int i = a.length()1, j = b.length()1; int carry = 0; while ( i >= 0  j >= 0) { int x = (i >= 0) ? a[i]  '0': 0; int y = (j >= 0) ? b[j]  '0': 0; output.push_back('0' + ((x + y + carry) % 2)); carry = (x + y + carry) / 2; i; j; } if (carry == 1) { output.push_back('0' + carry); } reverse(output.begin(), output.end()); return output; } };

@leaper thanks... But insert operation internally takes O(n) time as it shifts all other items backwards and then inserts the new element in the front. So for every insert this O(n) operation will take place, which is very costly.
On the other hand, by using reverse, we can reduce those O(n) operations to just once.
