Find the first repeating number in a given array

There can be multiple repeating numbers in an array but you have to find the first occurence of number which is repeating (occuring second time)

INPUT: 5 4 2 8 9 7 12 5 6 12 0 7

OUTPUT: 5 is the first repeating element

ALGORITHM 1

TIME COMPLEXITY – O(N)

SPACE COMPLEXITY – O(N)

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 2

TIME COMPLEXITY – O(NlogN)

SPACE COMPLEXITY – O(N)

1. Use Map by making value of 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

#include <bits/stdc++.h>
using namespace std;

int main()
{
	
	int arr[] = {5,16,18,21,64,57,16,7};
	int N = sizeof(arr)/sizeof(arr[0]);
	
	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] << " was the first element to be repeated\n";
					return 0;
				}
			else
				M.insert(make_pair(arr[i],true)); //else insert it into the map setting the value as true
		}
	
	
	cout<<"No element was repeated\n";
	return 0;
	
}
Try It

ALGORITHM 3

TIME COMPLEXITY – O(N 2 )

SPACE COMPLEXITY – O(1)

1.Run two loops in which outer loop selects an element.

2.The inner loop runs from the next index of the selected element and checks if we get another element equal to the selected element.

3.If we get same element that means the selected element is the first repeating element.

#include <bits/stdc++.h>
using namespace std;

int main()
{
	
	int arr[] = {5,16,18,21,64,57,16,7};
	int N = sizeof(arr)/sizeof(arr[0]);
	
	for(int i=0;i<N;i++) // select every number one by one
		for(int j=i+1;j<N;j++) // loop from the next to the end comparing if it is occuring again
			if(arr[i] == arr[j])
				{
					cout << arr[i] <<" was the first element to be repeated\n";
					return 0;
				}
	
	cout<<"No element was repeated\n";
	return 0;
	
}
Try It




Next > < Prev
Scroll to Top