Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Example
3.
Approach 1 - Hash Map
3.1.
Program
3.2.
Complexity Analysis
4.
Approach 2 - HashSet
4.1.
Program
4.2.
Complexity Analysis
5.
Approach 3 - Compare
5.1.
Program
5.2.
Complexity Analysis
6.
Frequently Asked Questions
6.1.
Can I store duplicate elements in an unordered set in C++?
6.2.
What is HashSet?
6.3.
What is the difference between Array and Vector?
7.
Conclusion
Last Updated: Mar 27, 2024

N Repeated Elements in Size 2N

Leveraging ChatGPT - GenAI as a Microsoft Data Expert
Speaker
Prerita Agarwal
Data Specialist @
23 Jul, 2024 @ 01:30 PM

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.

Check out Data Structures

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

illustration image

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

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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.

Live masterclass