## Approach 1 - Hash Map

The most apparent approach to the problem is storing each element’s count in an unordered map or hash map and the loop through the map to find the element with count ‘N’.

Let’s see how we are going to implement this.

- First, create an unordered map ‘MP.’
- Loop through the array elements and count their occurrence.
- Now loop through the unordered map ‘MP’ and see which elements occur ‘N’ time and return it.

See HashMap.

### Program

```
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
// Function that returns N repeated element in size 2N array.
int findNRepeatedElement(vector<int> &arr)
{
// Compute the value of N.
int n = arr.size() / 2;
// Initialize hash map.
unordered_map<int, int> mp;
// Loop through the array elements and count the number of occurrences for each element.
for (int &x: arr)
{
mp[x]++;
}
// Loop through the elements of the hash map and see which number has a count of 'N' and return that number.
for (const pair<int, int> &x: mp)
{
if (x.second == n)
{
return x.first;
}
}
// If no element found, return -1.
return -1;
}
int main()
{
// Taking user input.
int n;
cout << "Enter the value of N: ";
cin >> n;
vector<int> arr(2 * n);
cout << "Enter the array elements: ";
for (int i = 0; i < (2 * n); i++)
{
cin >> arr[i];
}
int ans = findNRepeatedElement(arr);
cout << "The Number which occurs N times is: " << ans << endl;
return 0;
}
```

**Input**

```
Enter the value of N: 3
Enter the array elements: 5 6 3 7 3 3
```

**Output**

`The Number which occurs N times is: 3`

### Complexity Analysis

**Time Complexity**

The Time Complexity is O(N), where 2N is the size of the array.

Since we are traversing the array once and hash map once.

**Space Complexity**

O(N), where 2N is the size of the array.

Since we are using an *unordered_map* to store the frequency of each element.

## Approach 2 - HashSet

One thing to observe is that there are a total of ‘2N’ elements, and since the repeated elements occur ‘N’ time, all the elements will occur only once in the array. So if we somehow store the elements we’ve seen before, then when an element repeats the first time, we know this is the ‘N’ repeated element. To store the previously seen element, we can use an unordered set in C++ or a hash set in Java.

Let’s see how the algorithm looks.

- Initialize an unordered set ‘ST’.
- Now loop through the array and insert elements in ‘ST’.
- If you’ve seen the element before, i.e., the current element is already in the set ‘ST’, return it.

Checkout HashSet

### Program

```
#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;
// Function that returns 'N' repeated element in 2N size array.
int findNRepeatedElement(vector<int> &arr)
{
// Compute the value of N.
int n = arr.size() / 2;
// Initialize unordered_set.
unordered_set<int> st;
// Loop through the array elements.
for (int &x : arr)
{
// If you encounter the number a second time, return it.
if (st.find(x) != st.end())
{
return x;
}
// Insert each number in the set to mark it seen.
st.insert(x);
}
// Return -1, if no 'N' repeated element found.
return -1;
}
int main()
{
// Taking user input.
int n;
cout << "Enter the value of N: ";
cin >> n;
vector<int> arr(2 * n);
cout << "Enter the array elements: ";
for (int i = 0; i < (2 * n); i++)
{
cin >> arr[i];
}
int ans = findNRepeatedElement(arr);
cout << "The Number which occurs N times is: " << ans << endl;
return 0;
}
```

**Input**

```
Enter the value of N: 4
Enter the array elements: 5 6 9 6 8 6 7 6
```

**Output**

`The Number which occurs N times is: 6`

### Complexity Analysis

Time Complexity

O(N), where 2N is the size of the array.

Since we are traversing the array only once and within that we are performing insert and search operations in the hash set, which is a constant operation.

Space Complexity

O(N), where 2N is the size of the array.

Since we are using an *unordered_set* to mark the elements as visited.

Check out this problem - __Subarray With 0 Sum__

## Approach 3 - Compare

There is a total of 2N numbers, and each of them is occurring exactly once except for the **major element**, so the major element’s count in the array is **N / 2 + 1**. Hence if we consider every subarray of length 4, there must be a major element in at least one of them. A length two subarray has a major element, or every length two subarrays have precisely one major element so a length four subarray that starts at a major element would have two major elements. Thus, we only have to compare elements with their neighbors that distance 1, 2, or 3 away.

### Program

```
#include <iostream>
#include <vector>
using namespace std;
// Function that returns N repeated element in size 2N array.
int findNRepeatedElement(vector<int> &arr)
{
// Compute the value of N.
int n = arr.size() / 2;
// Loop through 1 to 3 to compare elements with their neighbors at distances one, two, and three.
for (int x = 1; x <= 3; x++)
{
// Loop through the array.
for (int i = 0; i < (arr.size() - x); i++)
{
// If we found the repeated element Return it.
if (arr[i] == arr[x + i])
{
return arr[i];
}
}
}
// Return -1, if no 'N' repeated element is found.
return -1;
}
int main()
{
// Taking user input.
int n;
cout << "Enter the value of N: ";
cin >> n;
vector<int> arr(2 * n);
cout << "Enter the array elements: ";
for (int i = 0; i < (2 * n); i++)
{
cin >> arr[i];
}
int ans = findNRepeatedElement(arr);
cout << "The Number which occurs N times is: " << ans << endl;
return 0;
}
```

**Input**

```
Enter the value of N: 2
Enter the array elements: 7 8 9 9
```

**Output**

`The Number which occurs N times is: 9`

### Complexity Analysis

**Time Complexity**

O(N), where 2N is the size of the array.

Since the outer loop only ranges from 1 to 3 no matter what the value of ‘N’. And we are traversing the array once. Therefore, the overall time complexity is O(3 * N) = O(N).

**Space Complexity**

O(1).Since we are not using any extra space.

You can also read about the __Longest Consecutive Sequence__.

## Frequently Asked Questions

### Can I store duplicate elements in an unordered set in C++?

No, you can’t do that because the set is implemented in such a way in the standard library that it can only store unique elements.

### What is HashSet?

Unordered collections consisting of unique elements are referred to as HashSet.

### What is the difference between Array and Vector?

The array is static in size, whereas the vector is dynamic in size.

## Conclusion

Because an array is a simple data structure, array problems can be solved in various ways. I hope you had a good time solving this problem. Head over to Coding Ninjas Studio to read other such exciting blogs.

Coding Ninja has recently announced a course in DSA practice for Interviews. Do check it out.

Recommended Reading:

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Thanks for reading.