Java Solution 1ms O(1) space (Bit Manipulation)


  • 0
    A

    We use a similar (inspired) approach as we did while solving the problem Maximum Product of Word Lengths. We use an integer value which stores bit 1's only at the positions of nums[i] and 0's at the positions where the nums[i] is missing. For example if the input is [4,3,2,7,8,2,3,1], we create an integer having bits as 11001111, where i'th bit in this number (from right to left ) represents the occurence of nums[i] ( 11001111 has 5th and 6th positions set as 0's reading from LSD bit to MSD bit). If any bit at ith position is 0, it represents that number is missing.

    As for our first element in the array nums, the number 8 was encountered. We do a left-shift of '1' by 7( nums[i]-1) positions to place it at the 8th bit, the value becomes 1000000 and then OR (inclusive) it with the original value ( Thus, the result is invariant to duplicates ). After we traverse through the array, we get the result which stores the bits as 0's at positions whereever the numbers were not present in nums[i].

    We then simply return those bit positions set as 0 in a list as our result. The extra check we need to have is the length of number of bits of our result. In the case like, [1,1,2,2] the resultant value would be 11, but we need to check for 4 positions as the nums.length is 4 in this case. So, we add additional OR condition to traverse till the length of the array (at max).

    Here is the solution,

        public List<Integer> findDisappearedNumbers(int[] nums) {
            List<Integer> list = new ArrayList<Integer>();
            int value = 0, index = 1, len = nums.length;
            for( int i = 0; i < len; i++ )
                value |= (1 << (nums[i]-1));
            
            while( value > 0 || len > 0)
            {
                if ((value & 1) == 0)
                    list.add(index);
                index++;
                len--;
                value >>= 1;
            }
            return list;
        }
    

  • 1
    M

    hi, you use a int bit to present whether the nums[i] is missing. but i think it's not enough, the nums.length can be greater than 32. if that, your solution is wrong. eg. input:

    [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 32]

    may be the problem should say n <= 32?


  • 0
    A

    @magicly agreed! I guess, we don't have enough test cases right now to cover large inputs ( nums.length > 32)


Log in to reply
 

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