LeetCode June Challenge - Day 25

Problem: LeetCode June Challenge - Day 25

Ideas

  1. Store n in nums[n-1] for each n. If some element is duplicated, the second time you will find it in nums[n-1].

Solution:

class Solution {
    public:
        int findDuplicate(vector<int>& nums) {
            int n = nums.size();
            for(int i=0; i<n; ++i)
                while(i+1 != nums[i]){
                    if(nums[nums[i]-1] == nums[i])
                        return nums[i];
                    swap(nums[i], nums[nums[i]-1]);
                }
            return -1;
        }
};