Find duplicate in an array.

Problem Statement :-

Given an array of integers containing n + 1 integers where each integer is in the range [1, n] inclusive. Any integer can appear any number of times, find the repeated/duplicate numbers in the array.

Link to the problem

Approaches to the above problem or similar problem has been added below.

---

Approach 1 :-

Loop through all elemnts of the array. On seeing abs(nums[i]), make element at ith index negative. If the element is already negative,that means the number has been visited. Return this element as the repeated number.

Time Complpexity = O(n)
Space Complexity = O(1)

int findDuplicate(vector<int>& nums) {
 for(int i:nums){
       if(nums[abs(i)] > 0){
          nums[abs(i)] *= -1;
       }else{
          return abs(i);
       }
    }
    return -1;
 }

---

Approach 2 :-

In this approach the input array is used as a hashmap.The idea is to loop through all the elements of the array and for every encountered
number (num) add n (size of nums array) to the
(num % n)th element.
Again loop through all the elements of the modified array to check if nums[i]/n > 1, which implies n has been added more than once.

Time Complpexity = O(n)
Space Complexity = O(1)

void findDuplicates(vector<int> &nums){
  int n = nums.size();
  for(int num:nums){
    nums[num%n] += n;
  }
  for(int i=0 ; i < n; i++){
    if(nums[i]/n > 1)
      cout << i <<" ";
  }
}

---

Approach 3 :-

This approach makes use of Pigeonhole Principle and binary search.

Time Complpexity = O(nlogn)
Space Complexity = O(1)

int findDuplicate(vector<int>& nums){
    int n = nums.size();
    int low = 0, high = n-1, mid;
    while(low < high){
        int count = 0;
        mid = (low + high) / 2;
        // count numbers which are less than or equal to mid 
        for(int num:nums){
            if(num<=mid)
                count++;
        }
        // if count is greater than mid then the duplicate
        // element should be in the [low .. mid] region else 
        //duplicate element should be in the [mid+1 .. high] region
        if(count > mid)
            high = mid;
        else
            low = mid + 1;
    }
    return low;
}