Clean O(n) solution in C++


  • 1
    J

    The trick is to swap a with b if b is larger to simplify the logic, as well as to add extra item in front of a in advance. I think this solution looks quite clean and straightforward, or, in this case, it is better to say straightbackward.

    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++;
            
            // add b to a
            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;
        }
    };

Log in to reply
 

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