Find the first Repeating Number in a Given Array

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

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

#include <bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  cin>>n;
  int a[n];
  for(int i=0;i<n;i++)
  {
      cin>>a[i];
  }
  unordered_map<int,int> m;
  int ans=0;
  for(int i=0;i<n;i++)
  {
      m[a[i]]++;
      if(m[a[i]]>1)
      {
          ans=a[i];
          break;
      }
  }
  if(ans==0)
  {
      cout<<"No element repeated"<<endl;
  }
  else
  {
    cout<<ans<<endl;
  }
}

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.

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