A concise O(N) solution


  • 0
    S
    string addBinary(string a, string b) {
        if (a.size() < b.size()) swap(a, b);
        int t = 0, total =0;
        int i = a.size() - 1, j = b.size() - 1;
        
        // add all the elements in b to a
        while (j >= 0) {
            total = (a[i] - '0') + (b[j] - '0') + t; 
            if (total >= 2) {
                a[i] = '0' + (total % 2);
                t = total / 2;
            }
            else {
                a[i] = '0' + total;
                t = 0;
            }
            --i, --j;
        }
        
        if(t == 0) return a;
        
        // add t to the remaining elements in a
        while (i >= 0) {
            if (a[i] == '1')
                a[i--] = '0';
            else {
                a[i--] = '1';
                return a;
            }
        }
        
       // the most important module is "1"
        return "1" + a;
    }

Log in to reply
 

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