|
This post is completed by 1 user
|
Add to List |
219. 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 the 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).
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 have count = 2.
Time Complexity: O(N), Space Complexity: O(N)
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)
Approach 4:
Array element as an index
- This solution works only if an array has positive integers and all the elements in the array are in the range from 1 to n.
- Navigate the array.
- Update the array as for ith index :- A[abs(A[i])] = A[abs(A[i])] * -1;
- (If it is already not negative).
- If A[x] is already negative, then it means we are visiting it a second time, which means it is repeated.
- Similar approach used in problem: If array has all consecutive numbers.
Time Complexity: O(N), Space Complexity: O(1)
Approach 5:
Using XOR
- This solution works only if the array has positive integers and all the elements in the array are in the range from 1 to n.
- As we know A XOR A = 0. We have n + 2 elements in an array with 2 repeated elements (say repeated elements are X and Y) and we know the range of elements is from 1 to n.
- XOR all the numbers in array numbers from 1 to n. The result is 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 the 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 a second group which has the elements for which the kth bit is 0.
- Let’s have that kth bit as the rightmost 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)
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 the same.
Time Complexity: O(nlogn), Space Complexity: O(1)