Share my C++ concise solution


  • 0
    O
    class Solution {
    public:
        string addBinary(string a, string b) {
            int carry = 0;
            string ans = a.size() > b.size() ? a : b;
            reverse(a.begin(), a.end());
            reverse(b.begin(), b.end());
            for (int i = 0; i < max((int)a.size(), (int)b.size()); i++) {
                int x = i < a.size() ? a[i] - '0' : 0;
                int y = i < b.size() ? b[i] - '0' : 0;
                ans[i] = (x ^ y) ^ carry + '0';
                carry = (x & y) | (carry & (x ^ y));
            }
            if (carry)
                ans += "1";
            reverse(ans.begin(), ans.end());
            return ans;
        }
    };

  • 0
    A

    Thanks for the approach.
    We can use reverse function just once and compare string values from the end as follows.
    This approach can save us some valuable execution time (P.S. There is no time difference in leetcode).

    class Solution {
    public:
        string addBinary(string a, string b) {
            
            string output ;
    
            int i = a.length()-1, j = b.length()-1;
            int carry = 0;
            
            while ( i >= 0 || j >= 0)
            {
                int x = (i >= 0) ? a[i] - '0': 0;
                int y = (j >= 0) ? b[j] - '0': 0;
                
                output.push_back('0' + ((x + y + carry) % 2));
                carry = (x + y + carry) / 2;
                
                i--;
                j--;
            }
            
            if (carry == 1)
            {
                output.push_back('0' + carry);
            }
            reverse(output.begin(), output.end());
            
            return output;
        }
    };
    

  • 0
    L

    you can put carry in the while (i >= 0 || j >= 0 || carry) {}. Also, using output.insert(0, 1, char((x+y+carry)%2+'0') will save the reverse.


  • 0
    A

    @leaper thanks... But insert operation internally takes O(n) time as it shifts all other items backwards and then inserts the new element in the front. So for every insert this O(n) operation will take place, which is very costly.

    On the other hand, by using reverse, we can reduce those O(n) operations to just once.


  • 0
    L

    @ashwinbansod Good point, thanks.


Log in to reply
 

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