# Find duplicate number in array

Written by

studymite

## Brute Force Approach

Sort the given array and run a loop to find the duplicate number.

TC – O(nlogn)  |  SC – O(1)

## Better Approach

#### Using HashMap

• Initialize an empty hashmap.
• Iterate over the elements of the array.
• For each element, increase its occurrence count in the hashmap by 1.
• Iterate over the elements of the hashmap.
• For each element in the hashmap, check if its occurrence count is greater than 1. If it is, print the element as a duplicate.
• If no duplicates are found, print a message indicating this.

TC – O(n)

SC – O(n)

## Optimal Approach

#### Using Floyd Cycle detection

We will take two pointers one will move fast and one slow.

``````#include<bits/stdc++.h>
using namespace std;

int findDuplicates(int arr[], int arrSize){
int fast = 0,
slow = 0;
do{
slow = arr[slow];
fast = arr[arr[fast]];

} while(slow != fast);

slow = 0;
while(slow != fast){
slow = arr[slow];
fast = arr[fast];
}

return slow; //or fast
}

int main(){
int arrWithDuplicates[] = {2,5,1,1,4,3};
int arrSize = sizeof(arrWithDuplicates)/sizeof(arrWithDuplicates[0]);
cout<<findDuplicates(arrWithDuplicates, arrSize);
return 0;
}
``````

Output

``````1
``````

TC – O(n)

SC – O(1)