Find the only repetitive element between 1 to n-1

Software Development
#1

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.

  1. Compute XOR of elements from 1 to n-1.
  2. Compute XOR of array elements.
  3. 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.

  1. Iterate through the array.
  2. 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)