67. Add Binary

Given two binary strings, return their sum (also a binary string).

For example,
a = "11"
b = "1"
Return "100"

Approach : The idea is to start from the right and keep adding digits and forwarding carry (if any). Also, take care of the case when one of them gets exhausted. For that, keep adding zero to the other one and forward carry if required. 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47

string Solution::addBinary(string a, string b) { int lenA = a.length(), lenB = b.length(); int i = lenA - 1, j = lenB - 1; int carry = 0; stack<char> out; int sum = 0; while(i >= 0 || j >= 0){ if(i >= 0 && j >= 0){ //convert to int and add sum = a[i] - '0' + b[j] - '0' + carry; i--; j--; } else{ //string a is exhausted if(i < 0){ sum = b[j] - '0' + carry; j--; } //string b is exhausted else{ sum = a[i] - '0' + carry; i--; } } //setting the carry accordingly if(sum > 1){ carry = 1; }else{ carry = 0; } sum = sum % 2; //convert back to character char aChar = '0' + sum; out.push(aChar); } //for final carry if(carry){ out.push('1'); } string res = ""; //reverse the output while(!out.empty()){ res = res + out.top(); out.pop(); } return res; }

Here is the link to the ideone solution : http://ideone.com/o5r3Eq