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

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

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

## Java

 `// Java program to find the only repeating  ` `// element in an array where elements are  ` `// from 1 to n-1. ` `import` `java.io.*; ` `import` `java.util.*;  ` ` `  `class` `GFG  ` `{ ` ` `  `    ``static` `int` `findRepeating(``int``[] arr, ``int` `n) ` `    ``{ ` `        ``// Find array sum and subtract sum  ` `        ``// first n-1 natural numbers from it  ` `        ``// to find the result. ` ` `  `        ``int` `sum = ``0``; ` `        ``for` `(``int` `i = ``0``; i < n; i++) ` `            ``sum += arr[i]; ` `        ``return` `sum - (((n - ``1``) * n) / ``2``);  ` `    ``} ` ` `  `    ``// Driver code ` `    ``public` `static` `void` `main(String args[])  ` `    ``{ ` `        ``int``[] arr = { ``9``, ``8``, ``2``, ``6``, ``1``, ``8``, ``5``, ``3``, ``4``, ``7` `}; ` `        ``int` `n = arr.length; ` `        ``System.out.println(findRepeating(arr, n)); ` `    ``} ` `} ` ` `  `// This code is contributed by rachana soma `

## Python3

 `# Python3 program to find the only  ` `# repeating element in an array where  ` `# elements are from 1 to n-1. ` ` `  `def` `findRepeating(arr, n): ` `     `  `    ``# Find array sum and subtract sum ` `    ``# first n-1 natural numbers from it ` `    ``# to find the result. ` `    ``return` `sum``(arr) ``-``(((n ``-` `1``) ``*` `n) ``/``/` `2``) ` ` `  `# Driver Code ` `arr ``=` `[``9``, ``8``, ``2``, ``6``, ``1``, ``8``, ``5``, ``3``, ``4``, ``7``] ` `n ``=` `len``(arr) ` `print``(findRepeating(arr, n)) ` ` `  `# This code is contributed  ` `# by mohit kumar `

## C#

 `// C# program to find the only repeating  ` `// element in an array where elements are  ` `// from 1 to n-1. ` `using` `System;  ` ` `  `class` `GFG  ` `{ ` ` `  `    ``static` `int` `findRepeating(``int``[] arr, ``int` `n) ` `    ``{ ` `        ``// Find array sum and subtract sum  ` `        ``// first n-1 natural numbers from it  ` `        ``// to find the result. ` ` `  `        ``int` `sum = 0; ` `        ``for` `(``int` `i = 0; i < n; i++) ` `            ``sum += arr[i]; ` `        ``return` `sum - (((n - 1) * n) / 2);  ` `    ``} ` ` `  `    ``// Driver code ` `    ``public` `static` `void` `Main(String []args)  ` `    ``{ ` `        ``int``[] arr = { 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 }; ` `        ``int` `n = arr.Length; ` `        ``Console.WriteLine(findRepeating(arr, n)); ` `    ``} ` `} ` ` `  `/* This code contributed by PrinciRaj1992 */`

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 ` `using` `namespace` `std; ` ` `  `int` `findRepeating(``int` `arr[], ``int` `n) ` `{ ` `   ``unordered_set<``int``> s; ` `   ``for` `(``int` `i=0; i

## Java

 `import` `java.util.*; ` `// Java program to find the only repeating  ` `// element in an array where elements are  ` `// from 1 to n-1. ` ` `  `class` `GFG  ` `{ ` ` `  `static` `int` `findRepeating(``int` `arr[], ``int` `n)  ` `{  ` `    ``HashSet s = ``new` `HashSet(); ` `    ``for` `(``int` `i = ``0``; i < n; i++)  ` `    ``{  ` `        ``if` `(s.contains(arr[i]))  ` `            ``return` `arr[i];  ` `        ``s.add(arr[i]);  ` `    ``}  ` `     `  `    ``// If input is correct, we should  ` `    ``// never reach here  ` `    ``return` `-``1``;  ` `}  ` ` `  `// Driver code  ` `public` `static` `void` `main(String[] args)  ` `{ ` `    ``int` `arr[] = { ``9``, ``8``, ``2``, ``6``, ``1``, ``8``, ``5``, ``3``, ``4``, ``7` `};  ` `    ``int` `n = arr.length; ` `    ``System.out.println(findRepeating(arr, n));; ` `} ` `} ` ` `  `// This code is contributed by Rajput-Ji `

## Python3

 `# Python3 program to find the only  ` `# repeating element in an array  ` `# where elements are from 1 to n-1.  ` `def` `findRepeating(arr, n): ` `    ``s ``=` `set``() ` `    ``for` `i ``in` `range``(n): ` `        ``if` `arr[i] ``in` `s: ` `            ``return` `arr[i] ` `        ``s.add(arr[i]) ` `     `  `    ``# If input is correct, we should  ` `    ``# never reach here  ` `    ``rteurn ``-``1` ` `  `# Driver code ` `arr ``=` `[``9``, ``8``, ``2``, ``6``, ``1``, ``8``, ``5``, ``3``] ` `n ``=` `len``(arr) ` `print``(findRepeating(arr, n)) ` ` `  `# This code is contributed  ` `# by Shrikant13 `

## C#

 `// C# program to find the only repeating  ` `// element in an array where elements are  ` `// from 1 to n-1. ` `using` `System; ` `using` `System.Collections.Generic; ` ` `  `class` `GFG  ` `{ ` ` `  `static` `int` `findRepeating(``int` `[]arr, ``int` `n)  ` `{  ` `    ``HashSet<``int``> s = ``new` `HashSet<``int``>(); ` `    ``for` `(``int` `i = 0; i < n; i++)  ` `    ``{  ` `        ``if` `(s.Contains(arr[i]))  ` `            ``return` `arr[i];  ` `        ``s.Add(arr[i]);  ` `    ``}  ` `     `  `    ``// If input is correct, we should  ` `    ``// never reach here  ` `    ``return` `-1;  ` `}  ` ` `  `// Driver code  ` `public` `static` `void` `Main(String[] args)  ` `{ ` `    ``int` `[]arr = { 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 };  ` `    ``int` `n = arr.Length; ` `    ``Console.WriteLine(findRepeating(arr, n));; ` `} ` `} ` ` `  `// This code has been contributed by 29AjayKumar `

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

## Java

 `// Java program to find the only repeating ` `// element in an array where elements are ` `// from 1 to n-1. ` `class` `GFG ` `{ ` `     `  `    ``static` `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 ` `    ``public` `static` `void` `main(String[] args) ` `    ``{  ` `        ``int` `arr[] = { ``9``, ``8``, ``2``, ``6``, ``1``, ``8``, ``5``, ``3``, ``4``, ``7` `}; ` `        ``int` `n = arr.length; ` `        ``System.out.println(findRepeating(arr, n)); ` `    ``} ` `} ` ` `  `// This code is contributed by  ` `// Smitha Dinesh Semwal. `

## Python3

 `# Python3 program to find the only  ` `# repeating element in an array where  ` `# elements are from 1 to n-1. ` ` `  `def` `findRepeating(arr, n): ` `     `  `    ``# res is going to store value of ` `    ``# 1 ^ 2 ^ 3 .. ^ (n-1) ^ arr[0] ^  ` `    ``# arr[1] ^ .... arr[n-1] ` `    ``res ``=` `0` `    ``for` `i ``in` `range``(``0``, n``-``1``): ` `        ``res ``=` `res ^ (i``+``1``) ^ arr[i] ` `    ``res ``=` `res ^ arr[n``-``1``] ` `         `  `    ``return` `res ` `     `  `# Driver code ` `arr ``=` `[``9``, ``8``, ``2``, ``6``, ``1``, ``8``, ``5``, ``3``, ``4``, ``7``]  ` `n ``=` `len``(arr)  ` `print``(findRepeating(arr, n)) ` ` `  `# This code is contributed by Smitha Dinesh Semwal. `

## C#

 `// C# program to find the  ` `// only repeating element  ` `// in an array where elements  ` `// are from 1 to n-1. ` `using` `System; ` ` `  `class` `GFG ` `{ ` `    ``static` `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 ` `    ``public` `static` `void` `Main() ` `    ``{  ` `        ``int` `[]arr = { 9, 8, 2, 6, 1,  ` `                      ``8, 5, 3, 4, 7 }; ` `        ``int` `n = arr.Length; ` `        ``Console.Write(findRepeating(arr, n)); ` `    ``} ` `} ` ` `  `// This code is contributed ` `// by Smitha Dinesh Semwal. `

## PHP

 ` `

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

## Java

 `// Java program to find the only  ` `// repeating element in an array  ` `// where elements are from 1 to n-1. ` `import` `java.lang.Math.*; ` ` `  `class` `GFG ` `{ ` `    ``// Function to find repeted element ` `    ``static` `int` `findRepeating(``int` `arr[], ``int` `n) ` `    ``{ ` `        ``int` `missingElement = ``0``; ` `     `  `        ``// indexing based ` `        ``for` `(``int` `i = ``0``; i < n; i++){ ` `     `  `            ``int` `element = arr[Math.abs(arr[i])]; ` `     `  `            ``if``(element < ``0``){ ` `                ``missingElement = arr[i]; ` `                ``break``; ` `            ``} ` `         `  `        ``arr[Math.abs(arr[i])] = -arr[Math.abs(arr[i])]; ` `    ``} ` `     `  `    ``return` `Math.abs(missingElement); ` `     `  `    ``} ` `     `  `    ``// Driver code ` `    ``public` `static` `void` `main(String[] args) ` `    ``{ ` `        ``int` `arr[] = { ``5``, ``4``, ``3``, ``9``, ``8``, ` `                    ``9``, ``1``, ``6``, ``2``, ``5``}; ` `     `  `        ``int` `n = arr.length; ` `     `  `        ``System.out.println(findRepeating(arr, n)); ` `     `  `    ``} ` `} ` `// This code is contributed by  ` `// Smitha Dinesh Semwal. `

## Python3

 `# Python3 program to find the only  ` `# repeating element in an array  ` `# where elements are from 1 to n-1. ` ` `  `# Function to find repeted element ` `def` `findRepeating(arr, n): ` ` `  `    ``missingElement ``=` `0` ` `  `    ``# indexing based ` `    ``for` `i ``in` `range``(``0``, n): ` ` `  `        ``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 ` `arr ``=` `[``5``, ``4``, ``3``, ``9``, ``8``, ``9``, ``1``, ``6``, ``2``, ``5``] ` `n ``=` `len``(arr) ` `print``(findRepeating(arr, n)) ` ` `  `# This code is contributed by Smitha Dinesh Semwal. `

## C#

 `using` `System; ` ` `  `// C# program to find the only  ` `// repeating element in an array  ` `// where elements are from 1 to n-1.  ` ` `  ` `  `public` `class` `GFG ` `{ ` `    ``// Function to find repeted element  ` `    ``public` `static` `int` `findRepeating(``int``[] arr, ``int` `n) ` `    ``{ ` `        ``int` `missingElement = 0; ` ` `  `        ``// indexing based  ` `        ``for` `(``int` `i = 0; i < n; i++) ` `        ``{ ` ` `  `            ``int` `element = arr[Math.Abs(arr[i])]; ` ` `  `            ``if` `(element < 0) ` `            ``{ ` `                ``missingElement = arr[i]; ` `                ``break``; ` `            ``} ` ` `  `        ``arr[Math.Abs(arr[i])] = -arr[Math.Abs(arr[i])]; ` `        ``} ` ` `  `    ``return` `Math.Abs(missingElement); ` ` `  `    ``} ` ` `  `    ``// Driver code  ` `    ``public` `static` `void` `Main(``string``[] args) ` `    ``{ ` `        ``int``[] arr = ``new` `int``[] {5, 4, 3, 9, 8, 9, ` `                                ``1, 6, 2, 5}; ` ` `  `        ``int` `n = arr.Length; ` ` `  `        ``Console.WriteLine(findRepeating(arr, n)); ` ` `  `    ``} ` `} ` ` `  `// This code is contributed by Shrikant13 `

## PHP

 ` `

Output :

```9
```

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