Use the 32nd bit


  • 0

    Given that the valid numbers are from 1 through n, and hence positive, we can make use of the unused "sign" bit to check the presence of duplicate! here is the code.

        vector<int> findDuplicates(vector<int>& nums) {
            vector <int> result;
            int i, len = nums.size();
            
            for (i = 0; i < len; i++) {
                int actNum = (nums[i]) & 0x7fffffff;
                int pos = nums[actNum - 1] & 0x80000000;
                if (pos)
                    result.push_back(actNum);
                nums[actNum - 1] |= 0x80000000;
            }
            
            return result;
        }
    

Log in to reply
 

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