Problem:

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

For example,

a = "11"

b = "1"

Return "100".

 

Analysis:

Three main steps: 1. add a and b until meet one's end; 2. process the remaining part of the the other string; 3. process the carry bit.

Simulation problem, the time complexity is O(n+m), the space complexity is O(n+m)

 

Code:

1 class Solution { 2 public: 3     string addBinary(string a, string b) { 4         // Start typing your C/C++ solution below 5         // DO NOT write int main() function 6         int la = a.length()-1, lb = b.length()-1; 7         int bitSum, carry = 0, idx=0; 8         char *res = new char[100](); 9         10         while (la>=0 && lb>=0) {11             bitSum = a[la] + b[lb] + carry - '0' - '0';12             if (bitSum == 2) {
    //there is a carry13                 res[idx++] = '0';14                 carry = 1;15             } else if (bitSum == 3) {16                 res[idx++] = '1';17                 carry = 1;18             } else {19                 res[idx++] = bitSum + '0';20                 carry = 0;21             }22             23             la--;24             lb--;25         }26         27         while (la>=0) {28             bitSum = a[la] + carry - '0';29             if (bitSum == 2) {
    //there is a carry30                 res[idx++] = '0';31                 carry = 1;32             } else {33                 res[idx++] = bitSum + '0';34                 carry = 0;35             }36             37             la--;38         }39         40         while (lb>=0) {41             bitSum = b[lb] + carry - '0';42             if (bitSum == 2) {
    //there is a carry43                 res[idx++] = '0';44                 carry = 1;45             } else {46                 res[idx++] = bitSum + '0';47                 carry = 0;48             }49             50             lb--;51         }52         53         if (carry > 0) res[idx++] = carry + '0';54         res[idx] = '\0';55         56         for (int i=0, j=idx-1; i <=j; i++, j--) {57             char ch = res[i];58             res[i] = res[j];59             res[j] = ch;60         }61 62         string sres = res;63         return sres;64     }65 };

 

 

Attention: