Java Solution - 204ms with minimal memory footprint & O(n) time & memory


  • 0
    J

    Basic idea is to stream the output directly to a fixed-size char[], so that it can be used to create the return String directly, and no type conversion or casting involved, no dynamic expansion of collection, just pure if-else comparisons.

    As for the memory footprint, the char[] buffer is the only O(n) piece in my code. (Although the String(char[]) implementation will do an Arrays.copyOfRange() to create another char[] as String's internal store, but it can't be avoided.)

        // the maximum possible result will have only one extra digit, so the char[] size just need 
        // to be bigger than the longest input by 1.
        char[] buffer = new char[Math.max(a.length(), b.length()) + 1];
        int i = buffer.length - 1, ai = a.length() - 1, bi = b.length() - 1;
        int extra = 0;
        while (extra != 0 || ai >= 0 || bi >= 0) {
            int ca = (ai >= 0 && a.charAt(ai--) == '1') ? 1 : 0;
            int cb = (bi >= 0 && b.charAt(bi--) == '1') ? 1 : 0;
            int sum = extra + ca + cb;
            buffer[i--] = (sum % 2 == 1) ? '1' : '0';
            extra = sum >> 1;
        }
        return new String(buffer, i + 1, buffer.length - i - 1);

  • 0
    O

    You need to initialize ca, cb, sum outside the while.


Log in to reply
 

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