N Repeated Elements in Size 2N

Firdausia Fatima
Last Updated: May 13, 2022

Introduction

Have you ever heard of a thing called Pair Programming? Two programmers work on the same machine where one writes code(Driver) and the other direct (Navigator). Let’s solve this problem pair programming style. I’ll be the Navigator, and you be the driver.

Problem Statement

You are given an array ‘ARR’ of size ‘2N’. This array contains ‘N + 1’ unique elements with one element occurring ‘N’ time.

Return ‘N’ repeated element in the array size 2‘N’.

Example

Now that we’ve defined the problem, let’s solve it.

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.

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

Time Complexity

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.

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

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.

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 that 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 are 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

Time Complexity

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

Since the outer loop only ranges from 1 to 3 no matter whats 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.

Key Takeaways

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 CodeStudio to read other such exciting blogs. 

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

Thanks for reading.

Was this article helpful ?
0 upvotes