We are given an array arr[] of size n. Numbers are from 1 to (n-1) in random order. The array has only one repetitive element. We need to find the repetitive element.
Examples :
Input : a[] = {1, 3, 2, 3, 4} Output : 3 Input : a[] = {1, 5, 1, 2, 3, 4} Output : 1
Method 1 (Simple) We use two nested loops. The outer loop traverses through all elements and the inner loop check if the element picked by outer loop appears anywhere else.
Time Complexity : O(n*n)
Method 2 (Using Sum Formula):
We know sum of first n-1 natural numbers is (n – 1)*n/2. We compute sum of array elements and subtract natural number sum from it to find the only missing element.
- C++
// CPP program to find the only repeating
// element in an array where elements are
// from 1 to n-1.
#include <bits/stdc++.h>
using namespace std;
int findRepeating( int arr[], int n)
{
// Find array sum and subtract sum
// first n-1 natural numbers from it
// to find the result.
return accumulate(arr , arr+n , 0) -
((n - 1) * n/2);
}
// driver code
int main()
{
int arr[] = { 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 };
int n = sizeof (arr) / sizeof (arr[0]);
cout << findRepeating(arr, n);
return 0;
}
Output :
8
Time Complexity : O(n)
Auxiliary Space : O(1)
Causes overflow for large arrays.
Method 3 (Use Hashing):
Use a hash table to store elements visited. If a seen element appears again, we return it.
- C++
// CPP program to find the only repeating
// element in an array where elements are
// from 1 to n-1.
#include <bits/stdc++.h>
using namespace std;
int findRepeating( int arr[], int n)
{
unordered_set< int > s;
for ( int i=0; i<n; i++)
{
if (s.find(arr[i]) != s.end())
return arr[i];
s.insert(arr[i]);
}
// If input is correct, we should
// never reach here
return -1;
}
// driver code
int main()
{
int arr[] = { 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 };
int n = sizeof (arr) / sizeof (arr[0]);
cout << findRepeating(arr, n);
return 0;
}
Output :
8
Time Complexity : O(n)
Auxiliary Space : O(n)
Method 4(Use XOR):
The idea is based on the fact that x ^ x = 0 and x ^ y = y ^ x.
- Compute XOR of elements from 1 to n-1.
- Compute XOR of array elements.
- XOR of above two would be our result.
- C++
// CPP program to find the only repeating
// element in an array where elements are
// from 1 to n-1.
#include <bits/stdc++.h>
using namespace std;
int findRepeating( int arr[], int n)
{
// res is going to store value of
// 1 ^ 2 ^ 3 .. ^ (n-1) ^ arr[0] ^
// arr[1] ^ .... arr[n-1]
int res = 0;
for ( int i=0; i<n-1; i++)
res = res ^ (i+1) ^ arr[i];
res = res ^ arr[n-1];
return res;
}
// driver code
int main()
{
int arr[] = { 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 };
int n = sizeof (arr) / sizeof (arr[0]);
cout << findRepeating(arr, n);
return 0;
}
Output:
8
Time Complexity : O(n)
Auxiliary Space : O(1)
Method 5 : Using indexing.
- Iterate through the array.
- For every index visit a[index], if it is positive change the sign of element at a[index] index, else print the element.
- C++
// CPP program to find the only
// repeating element in an array
// where elements are from 1 to n-1.
#include <bits/stdc++.h>
using namespace std;
// Function to find repeted element
int findRepeating( int arr[], int n)
{
int missingElement = 0;
// indexing based
for ( int i = 0; i < n; i++){
int element = arr[ abs (arr[i])];
if (element < 0){
missingElement = arr[i];
break ;
}
arr[ abs (arr[i])] = -arr[ abs (arr[i])];
}
return abs (missingElement);
}
// driver code
int main()
{
int arr[] = { 5, 4, 3, 9, 8,
9, 1, 6, 2, 5};
int n = sizeof (arr) / sizeof (arr[0]);
cout << findRepeating(arr, n);
return 0;
}
Output :
9
Time Complexiy : O(n)
Auxiliary Space : O(1)