4.Find the Duplicate Number

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

There is only one duplicate number in nums, return this duplicate number.

Example 1:
Input: nums = [1,3,4,2,2]
Output: 2

Example 2:
Input: nums = [3,1,3,4,2]
Output: 3

Example 3:
Input: nums = [1,1]
Output: 1

Example 4:
Input: nums = [1,1,2]
Output: 1

Solution: (Using Hashset)

class Solution
{
public:
    int findDuplicate(vector<int> &nums)
    {

        unordered_set<int> s;

        for (int i = 0; i < nums.size(); i++)
        {
            if (s.find(nums[i]) == s.end())
            {
                s.insert(nums[i]);
            }
            else
            {
                return nums[i];
            }
        }

        return -1;
    }
};

Time Complexity: O(n) , Space Complexity: O(n)

Solution II : Floyd's Tortoise and Hare (Cycle Detection)

Here is how it works:

class Solution
{
public:
    int findDuplicate(vector<int> &nums)
    {

        int slow = nums[0];
        int fast = nums[0];

        slow = nums[slow];
        fast = nums[nums[fast]];

        while (fast != slow)
        {
            slow = nums[slow];
            fast = nums[nums[fast]];
        }
        
        //finding the starting point of loop
        int ptr1 = slow;
        int ptr2 = nums[0];
        
        while(ptr1!=ptr2){
            ptr1 = nums[ptr1];
            ptr2 = nums[ptr2];
        }
        return ptr1;
    } 
};

Time Complexity: O(n) , Space Complexity: O(1)