A pinch of invisible cheat


  • 7
    V

    I found a way to cheat by modifying the array but only during the algorithm time. The idea is simple : mark revealed case by inverting its content. If a case inverted more than once, then I've found the number that appears more than once.

    Here is a C++ implementation :

    class Solution {
    public:
        int findDuplicate(vector<int>& nums) {
            int n = -1;
            for(int i = 0; i < nums.size(); i++) {
                n = std::abs(nums[i]);
                if(nums[n] < 0) {
                    break;
                }
                else {
                    nums[n] *= -1;
                }
            }
            for(int j = 0; j < nums.size(); j++) {
                nums[j] = std::abs(nums[j]);
            }
            return n;
        }
    };

  • 0
    C

    "nums[n] *= -1" which will make all element negative. It should be "nums[nums[n]] *= -1"


Log in to reply
 

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