Short O(n) time, O(1) space C++ solution


  • 7

    I just write the sum into the longer one of the inputs. Don't worry about modifying them, as getting string means we're getting copies. The "O(1) space" of course refers to the space I use in addition to input and output. If the output doesn't need to be longer than the longer input, I even only use O(1) space in addition to only the input.

    struct Solution {
        string addBinary(string a, string b) {
            if (a.size() < b.size())
                swap(a, b);
            int i = a.size(), j = b.size();
            while (i--) {
                if (j) a[i] += b[--j] & 1;
                if (a[i] > '1') {
                    a[i] -= 2;
                    if (i) a[i-1]++; else a = '1' + a;
                }
            }
            return a;
        }
    };

  • 0
    P

    I optimise your solution's performance a little.

    string addBinary(string a, string b) {
        if (b.size() > a.size())
            swap(a,b);
        int i = a.size(), j = b.size();
        while (--i) {
            if (j) a[i] += b[--j] & 1;
            if (a[i] > '1') {
                a[i] -= 2;
                ++a[i-1];
            }
        }
        if (j) a[0] += b[0] & 1;
        if (a[0] > '1') {
            a[0] -= 2;
            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.