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:

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 <A.length ; i++) {
for (int j = i+1; j <A.length ; j++) {
if(A[i]==A[j]){
System.out.print(A[i] + " ");
}
}
}
}
public static void main(String[] args) {
int [] A = {1,5,2,4,8,9,3,1,4,0};
twoRepeating(A);
}
}

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:

import java.util.HashMap;
import java.util.Iterator;
import java.util.Set;
public class TwoRepeatingHashMap {
public static void twoElements(int [] A){
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i <A.length ; i++) {
if(map.containsKey(A[i])){
int count = map.get(A[i]);
map.put(A[i],++count);
}else
map.put(A[i],1);
}
System.out.print("Repeated Elements are : ");
Set set = map.keySet();
Iterator<Integer> 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:

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 <A.length ; i++) {
X += A[i];
Y *= A[i];
}
int sum = X S;
int product = Y/fact;
int subtract = (int)Math.sqrt(sum*sum 4*product);
a = (sum + subtract)/2;
b = sum a;
System.out.println("Two Repeating Elements are: " + a + " and " + b);
}
static int factorial(int n){
if(n==0)
return 1;
else
return n*factorial(n1);
}
public static void main(String[] args) {
int [] A = {1,4,5,6,3,2,5,2};
int n = 6;
twoElements(A, n);
}
}

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:

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 <A.length ; i++) {
if(A[Math.abs(A[i])]<0)
System.out.print(Math.abs(A[i]) + " ");
else
A[Math.abs(A[i])] = A[Math.abs(A[i])] * 1;
}
}
public static void main(String[] args) {
int [] A = {1,4,5,6,3,2,5,2};
int n = 6;
twoRepeating(A, n);
}
}

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)

Two repeated elements 2

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

Code:

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 <size ; i++)
XOR ^= A[i];
//Now XOR contains the X XOR Y
//get the right most bit number
right_most_bit = XOR & ~(XOR1);
//divide the elements into 2 groups based on the right most set bit
for (int i = 0; i <size ; i++) {
if((A[i] & right_most_bit)!=0)
X = X^A[i];
else
Y = Y^A[i];
}
for (int i = 1; i <=n ; i++) {
if((i&right_most_bit)!=0)
X = X^i;
else
Y = Y^i;
}
System.out.println("Two Repeated elements are: " + X + " and " + Y);
}
public static void main(String[] args) {
int [] A = {1,4,5,6,3,2,5,2};
int n = 6;
twoRepeating(A, n);
}
}

view raw
TwoRepeatingXOR.java
hosted with ❤ by GitHub

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:

import java.util.*;
public class TwoRepeatingSorting {
public static void twoRepeating(int [] A){
Arrays.sort(A);
System.out.print("Repeated Elements are: ");
for (int i = 0; i <A.length1 ; i++) {
if(A[i]==A[i+1])
System.out.print(A[i] + " ");
}
}
public static void main(String[] args) {
int [] A = {1,4,5,6,3,2,5,2};
twoRepeating(A);
}
}