# Find the two repeating elements in a given array | 6 Approaches

Objective: Given an array of n+2 elements. All elements of the array are in range 1 to n and all elements occur once except two numbers which occur twice. Write an algorithm to find the two repeating numbers.

Example:

```int [] A = {1,4,5,6,3,2,5,2};
int n = 6;
Output: Two Repeated elements are: 2 and 5
```

Approach 1:

Naive: This problem can be easily solved using two nested loops. Take each element at a time and compare it with all the other elements and if it appears twice, print it. This solution will work even if all the numbers are not in the range of 1 to n.

Time complexity is O(N^2).

Code:

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

 public class TwoRepeatingBruteForce { //this solution will work even if all the numbers are not in the range of 1 to n public static void twoRepeating(int [] A){ System.out.println("Repeated Elements: "); for (int i = 0; i

Approach 2:

Using Hash Map

• This solution will work even if all the numbers are not in the range of 1 to n.
• Keep the count of each element in the Hash Map.
• Print the elements which has count = 2.

Time Complexity: O(N),  Space Complexity: O(N)

Code:

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

 import java.util.HashMap; import java.util.Iterator; import java.util.Set; public class TwoRepeatingHashMap { public static void twoElements(int [] A){ HashMap map = new HashMap<>(); for (int i = 0; i iterator = set.iterator(); while(iterator.hasNext()){ int key = iterator.next(); if(map.get(key)==2){ System.out.print(key + " "); } } } public static void main(String[] args) { int [] A = {1,5,2,4,8,9,3,1,4,0}; twoElements(A); } }

Approach 3:

Using Math’s Formula:

• This solution will work only if all the numbers are in the range of 1 to n and are >0
• Let’s say two repeated elements are a, b
• Sum of 1 to n elements = S, Sum of all array elements = X, so a + b = X-S
• Product of 1 to n elements = n!, Product of all array elements = Y, so a * b = Y/n!
• Now we have 2 equations and 2 unknowns , we can solve to get a and b
• We know that a – b = sqrt( (a + b)^2 – 4ab )

Example:

```1.	int [] A = {1,4,5,6,3,2,5,2};
int n = 6;
2.	S = n*(n+1)/2 = 6 * 7/2 = 21
3.	X (sum of all array elements) = 28
4.	a + b = 28 – 21 = 7
5.	Product of 1 to 6  = !6 = 720
6.	Y (Product of all array elements) = 7200
7.	a * b = 7200/720 = 10
8.	So now, a + b = 7 and a * b = 10
9.	a - b = sqrt( (a + b)^2 - 4ab )
10.	a – b = sqrt(7*7 – 4*10) = sqrt(49-40) = sqrt(9) = 3
11.	a = (7 + 3)/2 = 5
12.	b = 7-5 = 2
13.	Elements are 5, 2

```

Time Complexity: O(N),  Space Complexity: O(1)

Code:

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

 public class TwoRepeatingByFormula { public static void twoElements(int [] A, int n){ int a,b; int X =0; int Y =1; int S = n*(n+1)/2; int fact = factorial(n); for (int i = 0; i

Approach 4:

Array element as index

• This solu­tion works only if array has pos­i­tive inte­gers and all the ele­ments in the array are in range from 1 to n.
• Nav­i­gate the array.
• Update the array as for ith index :- A[abs(A[i])] = A[abs(A[i])] * -1;
• (If it already not negative).
• If A[x] is already negative, then it means we are visiting it second time, means it is repeated.
• Sim­i­lar approach used in prob­lem : If array has all con­sec­u­tive numbers.

Time Complexity: O(N),  Space Complexity: O(1)

Code:

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

 public class TwoRepeatingElementsByIndex { //this solution will work only if all the numbers are in the range of 1 to n and are >0 //navigate the array if number is x then multiply the A[x] by -1. //If A[x] is already negative, then it means we are visiting it second time, means it is repeated. public static void twoRepeating(int [] A, int n){ System.out.print("Repeated Elements are: "); for (int i = 0; i

Approach 5:

Using XOR

• This solu­tion works only if array has pos­i­tive inte­gers and all the ele­ments in the array are in range from 1 to n.
• As we know A XOR A = 0. We have n + 2 elements in array with 2 repeated elements (say repeated elements are X and Y) and we know the range of elements are from 1 to n.
• XOR all the numbers in array numbers from 1 to n. Result be X XOR Y.
• 1 XOR 1 =  0 and 1 XOR 0 = 1 with this logic in the result of X XOR Y if any kth bit is set to 1  implies either kth bit is 1 either in X or in Y not in both.
• Use the above step to divide all the elements in array and from 1 to n into 2 groups, one group which has the elements for which the kth bit is set to 1 and second group which has the elements for which the kth bit is 0.
• Let’s have that kth bit as right most set bit (Read how to find right most set bit)
• Now we can claim that these two groups are responsible to produce X and Y.
• Group -1: XOR all the elements whose kth bit is 1 will produce either X or Y.
• Group -2: XOR all the elements whose kth bit is 0 will produce either X or Y.
• See the diagram below for more understanding.(Click on the diagram to see it larger)

Time Complexity: O(N),  Space Complexity: O(1)

Code:

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

 public class TwoRepeatingXOR { public static void twoRepeating(int [] A, int n){ int XOR = A[0]; int right_most_bit, X=0, Y=0, size = A.length; for (int i = 1; i <=n ; i++) XOR ^= i; for (int i = 0; i

Output:

Two Repeated elements are: 2 and 5

Approach 6:

Using Sorting

• This solution will work even if all the numbers are not in the range of 1 to n.
• Sort the array, this will bring all the repeated elements together.
• Now traverse the array and compare the adjacent elements and print them if they are same.

Time Complexity: O(nlogn),  Space Complexity: O(1)

Code:

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.