First Repeating Element

Problem Statement

We have given an array that contains n integers. We have to find the first repeating element in the given array. If there is no repeated element then print “No repeating integer found”.

Note: Repeating elements are those elements that come more than once. (Array may contain duplicates)

Example

Input

6

1 2 3 1 4 2

Output

1

Approach 1 for First Repeating Element

Run two loops such that select every element from the array and traverse ahead and check for a duplicate in the array.
a)    If found print as First repeating integer.
b)    Else print No repeating integer found.
As we are running two loops order is O(N^2) N is the size of the array.

Implementation

C++ Program for First Repeating Element

#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];
  }
  for(int i=0;i<n;i++) // select an element
    for(int j=i+1;j<n;j++) //traverse ahead and check for duplicate
        if(arr[i]==arr[j])
          {
            cout<<arr[i];
            return 0;
          }
  cout<<"No repeating integer found\n";
  return 0;
}

import java.util.Scanner;
class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int arr[] = new int[n];
        for(int i=0;i<n;i++)
        {
            arr[i] = sr.nextInt();
        }
        int temp=0;
        for(int i=0;i<n;i++) // select an element
        for(int j=i+1;j<n;j++) //traverse ahead and check for duplicate
            if(arr[i]==arr[j])
              {
                System.out.println(arr[i]);
                temp=1;
                i=n;j=n;
              }
        if(temp==0)
        System.out.println("No repeating integer found");
    }
}

5
10 3 5 3 2

3

Approach 2 for First Repeating Element

This is like Hashing, we store the count of the number and index along with array element.

Step 1:
Create a vector M such that it acts like map function which contains the index of the array element with the pair of count and index.
a)    Here index is the minimum index of the element which is repeated.
b)    Count is the number of times it is repeated.

Step 2: Create an iterator to traverse on the map.

Step 3: Run a loop such that we select every element of the array from left. And find the element in the array, if already present update its count.

Step 4: If the element is coming for the first time, then add it to the map.
a)     Count equal to 1
b)    An occurrence at index i, if you are at i.

Step 5: Get the minimum index by traversing into the map.
a)     Initialize the min_index to INT_MAX
b)    Traverse the map to find min_index so, find second of Map, then second of the second to get the index.
c)    Use the Inbuilt min function to compare the min_index.
d)    Finally, store it.

Step 6: Finally, if min_index not equal to INT_MAX, print it as the first repeating integer because there is some integer which is repeated. Else Print no repeating integer.

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];
  }
  unordered_map<int,pair<int,int> > M;
  unordered_map<int,pair<int,int> > ::iterator it;//iterator to traverse the map
  for(int i=0; i<n; i++)//select an element
    {
      it = M.find(arr[i]); //find the element
      
      if(it != M.end())//if element already present update its count
      {
        pair<int,pair<int,int> > temp = (*it);
        pair<int,int> p = temp.second;
        p.second++;
        M.erase(it);
        M.insert(make_pair(arr[i],p));
      }
      
      else //if element came for the first time then add it into the map with count 1 and occurence at i
      M.insert(make_pair(arr[i],make_pair(i,1))); 
    }
  
  int min_index = INT_MAX; //obtaint the minimum index
  for(it = M.begin(); it != M.end(); it++) //traverse the entire map
    {
    pair<int,pair<int,int> > temp = (*it);
    pair<int,int> p = temp.second;
    if(p.second > 1)
      min_index = min(min_index,p.first);  //minimum index of the element that is repeating
    }
    
  if(min_index != INT_MAX)
  cout<<arr[min_index];
  else  
  cout<<"No repeating integer found\n";
  return 0;
}

import java.util.Arrays;
import java.util.Scanner;
class sum
{
    public static int firstRepeated(int[] arr, int n)
    {
        int max = 0;
        for (int x = 0; x < n; x++) {
            if (arr[x] > max) {
                max = arr[x];
            }
        }
        int temp[]
            = new int[max + 1]; // the idea is to use
                                // temporary array as hashmap
        Arrays.fill(temp, 0);
        for (int x = 0; x < n; x++) {
            int num = arr[x];
            temp[num]++;
        }
        for (int x = 0; x < n; x++) {
            int num = arr[x];
            if (temp[num] > 1) {
                return x;
            }
        }
        return -1; // if no repeating element found
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int arr[] = new int[n];
        for(int i=0;i<n;i++)
        {
            arr[i] = sr.nextInt();
        }
        int index = firstRepeated(arr,n); // index Of 1st repeating number
        if (index != -1) 
        {
            System.out.println(arr[index]);
        }
        else 
        {
            System.out.println("No repeating integer found");
        }
    }
}

7
1 3 5 30 2 1 3

1