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?

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.

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.

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.

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.

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.

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.

## Duplicate Elements Array

hari_nowayoutProfile Answers by hari_nowayout Questions by hari_nowayout

Questions by hari_nowayout answers by hari_nowayout

## Related Answered Questions

## Related Open Questions