Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

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

Objec­tive: Given an array of n+2 ele­ments. All ele­ments of the array are in range 1 to n and all ele­ments occur once except two num­bers which occur twice. Write an algo­rithm to find the two repeat­ing numbers.

Exam­ple:

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 prob­lem can be eas­ily solved using two nested loops. Take each ele­ment at a time and com­pare it with all the other ele­ments and if it appears twice, print it. This solu­tion will work even if all the num­bers are not in the range of 1 to n.

Time com­plex­ity is O(N^2).

Code:

Approach 2:

Using Hash Map

  • This solu­tion will work even if all the num­bers are not in the range of 1 to n.
  • Keep the count of each ele­ment in the Hash Map.
  • Print the ele­ments which has count = 2.

Time Com­plex­ity: O(N),  Space Com­plex­ity: O(N)

Code:

Approach 3:

Using Math’s Formula:

  • This solu­tion will work only if all the num­bers are in the range of 1 to n and are >0
  • Let’s say two repeated ele­ments are a, b
  • Sum of 1 to n ele­ments = S, Sum of all array ele­ments = X, so a + b = X-S
  • Prod­uct of 1 to n ele­ments = n!, Prod­uct of all array ele­ments = Y, so a * b = Y/n!
  • Now we have 2 equa­tions and 2 unknowns , we can solve to get a and b
  • We know that a — b = sqrt( (a + b)^2 — 4ab )

Exam­ple:

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 Com­plex­ity: O(N),  Space Com­plex­ity: O(1)

Code:

Approach 4:

Array ele­ment 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 neg­a­tive, then it means we are vis­it­ing it sec­ond time, means it is repeated.
  • Sim­i­lar approach used in prob­lem : If array has all con­sec­u­tive numbers.

Time Com­plex­ity: O(N),  Space Com­plex­ity: O(1)

Code:

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 ele­ments in array with 2 repeated ele­ments (say repeated ele­ments are X and Y) and we know the range of ele­ments are from 1 to n.
  • XOR all the num­bers in array num­bers 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 ele­ments in array and from 1 to n into 2 groups, one group which has the ele­ments for which the kth bit is set to 1 and sec­ond group which has the ele­ments 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 respon­si­ble to pro­duce X and Y.
  • Group –1: XOR all the ele­ments whose kth bit is 1 will pro­duce either X or Y.
  • Group –2: XOR all the ele­ments whose kth bit is 0 will pro­duce either X or Y.
  • See the dia­gram below for more understanding.(Click on the dia­gram to see it larger)

Two repeated elements 2

Time Com­plex­ity: O(N),  Space Com­plex­ity: O(1)

Code:

Out­put:

Two Repeated ele­ments are: 2 and 5

Approach 6:

 Using Sort­ing

  • This solu­tion will work even if all the num­bers are not in the range of 1 to n.
  • Sort the array, this will bring all the repeated ele­ments together.
  • Now tra­verse the array and com­pare the adja­cent ele­ments and print them if they are same.

Time Com­plex­ity: O(nlogn),  Space Com­plex­ity: O(1)

Code:

You may also like...