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.
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; }
5 10 3 5 3 2
3
Complexity Analysis for First Repeating Element
Time Complexity: O(N^2) where N is the size of the array. Here we pick one element and check it whether it is equal to other elements that are present next to that element.
Space Complexity: O(1) because we don’t use any auxiliary space here.
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.
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; }
7 1 3 5 30 2 1 3
1
Complexity Analysis for First Repeating Element
Time Complexity: O(N) where N is the size of the given array. Here we count the number and check for the repeated element.
Time Complexity: O(N) because we use an unordered map to store the present elements.