Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Hide Buttons

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:

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:

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:

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:

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:

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:

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

You may also like...

%d bloggers like this: