# Find the only repetitive element between 1 to n-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);`

` ` `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);`

` ` `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 ^ `

` ` `// arr ^ .... 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);`

` ` `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);`

` `

` ` `cout << findRepeating(arr, n);`

` `

` ` `return` `0;`

`}`

Output :

9

Time Complexiy : O(n)
Auxiliary Space : O(1)