Find the first Repeating Number in a Given Array  

Difficulty Level Easy
Frequently asked in Adobe Amazon Apple Bloomberg Citadel eBay Facebook Goldman Sachs Google Intuit Microsoft Nutanix Oracle PayPal Salesforce Wish Yahoo
Array Hash Searching Zynga

Problem Statement  

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

Please click Like if you loved this article?

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.

Implementation

C++ Program

Java Program

import java.util.HashMap;
import java.util.Scanner;
class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        HashMap <Integer,Integer> m = new HashMap<Integer, Integer>();
        int ans=0;
        for(int i=0;i<n;i++)
        {
            int x = m.get(a[i])==null ? 1: m.get(a[i])+1;
            m.put(a[i], x);
            if(m.get(a[i])>1)
            {
                ans=a[i];
                break;
            }
        }
        if(ans==0)
        {
            System.out.println("No element repeated");
        }
        else
        {
          System.out.println(ans);
        }
    }
}
12
5 4 2 8 9 7 12 5 6 12 4 7
5

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.

See also
Find minimum number of merge operations to make an array palindrome

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.

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

Implementation

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;
  
}

Java Program

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        Map <Integer,Integer> m = new HashMap<Integer, Integer>() {}; // create a map with key as the array element and value as if it is present or not
        int frank=0;
        for(int i=0;i<n;i++)
        {
            boolean temp = m.containsValue(a[i]);
            if(temp) // if present then it is the first element to be repeated
            {
                System.out.println(a[i]);
                frank=1;
                i=n;
            }
            else
            {
               m.put(a[i],1); //else insert it into the map setting the value as true
            }
          }
        if(frank==0)
        System.out.println("No element repeated");
    }
}
6
1 2 3 4 5 6
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 into the map.

See also
Queries for Number of Distinct Elements in a Subarray

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

References

Please click Like if you loved this article?

Please click Like if you loved this article?