Home » Technical Interview Questions » Array Interview Questions » Find the first Repeating Number in a Given Array

Find the first Repeating Number in a Given Array


Reading Time - 2 mins

There can be multiple repeating numbers in an array but you have to find the first repeating number in a given array (occurring the second time).

Example

Input

12

5 4 2 8 9 7 12 5 6 12 4 7

Output

5 is the first repeating element

Approach 1 for Find the first Repeating Number

Simply we can Use Hashing where we hash the values of the elements of the array and incrementing the count of occurrence. As soon as we get an element with count 1 i.e. which has occurred already we get the first repeating element.

Algorithm

1. Traverse each element of the array.

2. Increase the frequency of each element.

3. If any element whose frequency greater than 1 then print that number directly.

C++ Program

Complexity Analysis for Find the first Repeating Number

Time Complexity– O(N) where N is the size of the array. Here we iterating over the array and store the frequency/count of the elements in hash map.

Space Complexity – O(N) because we count the frequency o element and maximum size possible of hash map is O(n).

Approaches 2 for Find the first Repeating Number

Here we use map which stores that element present in the array or not. If the element is present then it contains true with respect to that element in the map. If the element is not present then it maintains false with respect to that element in the map.

READ  Sort Colors

Algorithm

1. Use Map by making the value of the array element as the key and count as the key-value pair.

2. Initialize a pair with count as 1 and increment it.

3. As soon as we get an element whose count is 1 we get the first repeating element

C++ Program

#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,bool> M; // create a map with key as the array element and value as if it is present or not
  map <int,bool> :: iterator it;
  for(int i=0;i<n;i++)
    {
      it = M.find(arr[i]); //find the array element in map
      if(it != M.end()) // if present then it is the first element to be repeated
        {
          cout<<arr[i] <<endl;
          return 0;
        }
      else
        M.insert(make_pair(arr[i],true)); //else insert it into the map setting the value as true
    }
  cout<<"No element repeated"<<endl;
  return 0;
  
}
12 
5 4 2 8 9 7 12 -5 6 1 -4 -7
No element repeated

Complexity Analysis for Find the first Repeating Number

Time Complexity – O(NlogN) because insertion in map take O(logn) time and here we insert n elements int the map.

Space Complexity – O(N) because we use a map which stores that element is present on not.

References

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions