rem132

 Profile Answers by rem132 

• 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.

anuragthegr8

 Profile Answers by anuragthegr8 

• 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.

vikramb

 Profile Answers by vikramb 

• Jan 25th, 2009

 

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

silpachandrika

 Profile Answers by silpachandrika 

• 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.

shail81

 Profile Answers by shail81 

• 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.

Abhis3k

 Profile Answers by Abhis3k 

• Mar 4th, 2011

 

Just iterate through the array and compare i^th, i+1^th,  and i+2^th 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.
 

nsudheer

 Profile Answers by nsudheer 

• 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)

cullensun

 Profile Answers by cullensun 

• 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.