Solution - Zero Extra Space


  • 4
    C

    Here is how to make the constant space solution into a zero space solution. You simply treat A[0], A[1], and A[2] as the ones, twos, and threes masks. To do this, A[0] and A[1] must be preprocessed.

    public class Solution {
        public int singleNumber(int[] A) {
            if(A.length == 1) return A[0];
            // A[0] is correct to start
            // Take care of processing A[1]
            A[0] ^= A[1];
            // Set A[1] to either 0 or itself
            A[1] = (A[0]^A[1])&A[1];
    
            // Continue with algorithm as normal
            for(int i = 2; i < A.length; i++){
                A[1] |= A[0]&A[i];
                A[0] ^= A[i];
                A[2] = ~(A[0]&A[1]);
                A[0] &= A[2];
                A[1] &= A[2];
            }
            return A[0];
        }
    }

  • 0
    D

    How long did it took you to come up with this solution?


  • 0
    C

    Once I had an understanding of the constant space solution, it took just a minute or two to come up with this zero space solution. Though, I now realize it's not truly zero space as I declared the variable "i". This can easily be fixed though by using A[3] as "i" after preprocessing A[3].


  • 0
    D

    And how long did it took you to understand the constant space solution?


Log in to reply
 

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