My straightforward O(n) time, O(1) space C++ solution (please suggest improvements)


  • 0
    S

    I basically write "0" for shorter string and explicitly check for 3 possible cases.

    class Solution {
    public:
        string addBinary(string a, string b) {
            string result;
            
            int i = a.length()-1;
            int j = b.length()-1;
            
            string a_i, b_j;
            bool carry = false;
            
            while (i>=0 || j>=0){
                if (i>=0) {
                    a_i = a[i];
                } else {
                    a_i = "0";
                }
                if (j>=0){
                    b_j = b[j];
                } else {
                    b_j = "0";
                }
                
                if (a_i == "0" && b_j == "0"){
                    result = (carry? "1" : "0") + result;
                    carry  = false;
                } else if (a_i == "1" && b_j == "1"){
                    result = (carry? "1" : "0") + result;
                    carry = true;
                } else {
                    result = (carry? "0" : "1") + result;
                    //carry = (carry? true : false);
                }
                i--;
                j--;
            }
            
            return (carry? "1" + result : result);
        }
    };

  • 2
    J

    Exactly to remove extra IFs from the loop I decided to swap the strings and add shorter one to longer one.
    Here is my code with comments.

    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;
            }
        };

  • 0
    S
    string addBinary(string a, string b) {
    	string::reverse_iterator aiter = a.rbegin(), biter = b.rbegin();
    	for (; aiter != a.rend() && biter != b.rend(); ++aiter, ++biter)
    	{
    		if (*aiter == '1' && *biter == '1')
    			*aiter = '2';
    		else if (*aiter == '0' && *biter == '1')
    			*aiter = '1';
    	}
    	a = string(b.begin(), b.begin() + (b.rend() - biter)) + a;
    	char count = '0';
    	for (aiter = a.rbegin(); aiter != a.rend(); ++aiter)
    	{
    		if (*aiter == '2')
    		{
    			if (count == '1')
    				*aiter = '1';
    			else
    				*aiter = '0';
    			count = '1';
    		}
    		else if (*aiter == '1')
    		{
    			if (count == '1')
    				*aiter = '0';
    		}
    		else
    		{
    			*aiter = count;
    			count = '0';
    		}
    	}
    	if (count != '0')
    		a = "1" + a;
    	return a;
    }

Log in to reply
 

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