# Find duplicate in an array of N+1 Integers in C++

## Duplicate in an array of N+1 integers in C++

Here, in this page we will discuss the program to find the duplicate in an array of N+1 integers in C++ . We are Given an array of integers Arr containing N+1 integers where each integer is in the range [1, N] inclusive.

## Algorithm :

• Take the size of the array from the user and store it on variable say n.
• Declare an array of size N and take N elements from the user.
• Declare a map which holds the frequency of the elements present in the array.
• Now, iterate over the array and store the frequency of elements in the array in the map.
• Now, iterate the map and print those keys which have value greater than 1.

## Code in C++

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

int main ()
{

int n;
cin >> n;

int arr[n];

for (int i = 0; i < n; i++)
cin >> arr[i];

map < int, int >mp;

for (int i = 0; i < n; i++)
mp[arr[i]]++;

for (auto it = mp.begin (); it != mp.end (); it++)
{
if (it->second > 1)
cout << it->first << " ";
}
return 0;
}
```

### Output

`Output :51 1 2 5 51 5`

## Efficient Algorithm  to find duplicate in an array of N+1 integers in C++ :

• Traverse the given array from 0 to n.
• For every element in the array increment the (arr[i]-1)%n‘th element by n.
• Now traverse the array again and print all those indices i for which (arr[i]-1)/n is greater than 2. Which guarantees that the number n has been added to that index.
```#include <iostream>
using namespace std;

// function to find repeating elements
void printRepeating(int arr[], int n)
{
for (int i = 0; i < n; i++)
{
int index = (arr[i]-1) % n;
arr[index] += n;
}

for (int i = 0; i < n; i++)     {        if (((arr[i]-1) / n) >= 2)
cout << i+1 << " ";     } } // Driver code   int main()  {   int n;   cin>>n;

int arr[n];

for(int i=0; i<n; i++) cin>>arr[i];
cout << "The repeating elements are: \n";

// Function call
printRepeating(arr, n);
return 0;
}```

### Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription