Duplicate Elements Array

You have an array of size '2n' of these, 'n+1' elements are distinct and 1 element is repeated 'n' times. You must find the repeated element and say how many times it has repeated. Your solution must use minimum no. of comparisons. Also, say how many comparisons your solution will make in the worst case?

• Sep 2nd, 2008

Iterate through each bit of numbers, i.e. if we have 32-bit numbers then there will be 32 iterations. For the current bit B:

Iterate through the array and count numbers C0 and C1 - how many elements contain 0 and 1 in bit B. If C0 > N, then the repeating element contains 0 in this bit, if C1 > N, then it contains 1 in this bit. In both cases we continue the outer loop.

In the third case: if C0 = C1 = N, then we need one more check: go through the array and find any two numbers that contain 0 in bit B. If they are equal, then we found the answer. Otherwise find any number that contains 1 in bit B - this is the answer.

• Jan 11th, 2009

First, put the first and the last element in a separate array A, use binary search to find the middle element and compare it with element in this array A. If this element is a match, we have found the element, else, add the middle element in the array and then recursively call binary search in the 2 sub-arrays from 0-n/2 and n/2+1 to n and repeat the procedure till you find the element.

• Jan 25th, 2009

Iterate over the list: As you iterate, keep adding elements to a binary search tree, checking for duplicate additions.

• Feb 4th, 2009

Keep adding all the elements to a BST. When you see the element already present, you got the duplicate number.
If the question is extended to find all the duplicate numbers and the frequency of their occurence, have the tree node structure to include the frequency of the occurence, and keep incrementing when you find that element repeated.

• Mar 13th, 2009

The number of times the element is repeated is known. No? It is 'n'.

Given that info you find the product of all the numbers say 'P'.
Now find the largest number say x in the array such that P is divisible by x^n.

• Mar 4th, 2011

Just iterate through the array and compare ith, i+1th,  and i+2th element with each other, whichever is repeated, that is the repeated number.

Sumit Khedkar Profile Answers by Sumit Khedkar

• May 26th, 2011

Just sort the given arrya using comparison base sort techniques live quicksort.(nlog n)
while sorting check whether u get any 2 equal numbers if found stop there.
So now u know the number and it is already stated that the no. is repeated n times.
So the worst case time complexity is n log n.

• Jun 4th, 2011

In 2n elements, one element is repeated n times.

Let us assume that the repeated number is 4. The elements in array can be as given below (there can be other combinations).

1 4 2 4 3 4 5 4 6 4 ...

In all the combinations you can assume, the repeating element should appear twice at least in one or more three consecutive element sets in the array.

So iterate over the array, while iterating compare a[i] with a[i+1] and [i+2]. if a[i] == a[i+1] or a[i+2], then a[i] will be repeating element.

This works. Let me know, if you have question.

shankar

• Oct 16th, 2012

Since an element is repeated more than half the occurance of the array, for every two didtinct elements discard them from the array. At the end of the loop, the most repeated element will be left.

This is O(n)

• Sep 23rd, 2013

1st, 2nd, 3rd,......, (n-1)th, (n)th,
(n+1)th, (n+2)th, ...... (2n)th

Focus: Identify the the repeated element

1. take the 1st element to compare with the rest one by one, worst case: compare with (n+1)th, still unequal, has made n comparisons;
2. take the 2nd element to compare with the rest one by one, worst case: compare with the (n+1)th, still unequal, has made n-1 comparisons;
3. take the 3rd element to compare with the rest one by one, worst case: compare with the (n+1)th, still unequal, has made n-2 comparisons;
...
...
...
During above process once we find the repeated element, the problem is solved.
If all falls in the worst case. we will have to make n+ (n-1) + (n-2)+...+2+1= (n+1)*n/2 comparisons, and the repeated elements fall in the elements (n+1)th, .... (2n)th.