Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

We have N numbers(real numbers(float)).They can be positive or negative or anything we do not know except the fact that there is exactly one number which has a duplicate and the rest all are distinct. I would like to know the fastest one to find the duplicates.Can anyone help ? Thanks

share|improve this question
4  
Have you put any thought into how to do this? What have you come up with so far? –  DFord Feb 20 '13 at 19:44
    
Are they exactly duplicate? or is the candidate pair within some range that are nearly the same (floats aren't exact)? –  MichaelT Feb 20 '13 at 19:58
    
I can think something if N numbers are within 0 and N-1 and integers.And for matching let us say as you say within some range pairs are equal. –  Sameer Sen Feb 20 '13 at 20:08
    
Is the array sorted? If thats the case then you can iterate through the array just checking the next item in the array. Otherwise, you will need to iterate through the array. At each item, you will need to iterate through the rest of the array checking each pair. –  DFord Feb 20 '13 at 20:14
2  
Is this homework? –  Jimmy Hoffa Feb 20 '13 at 20:35
add comment

closed as too localized by GlenH7, Glenn Nelson, Martijn Pieters, gnat, Yusubov Feb 20 '13 at 21:46

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

3 Answers

If we were dealing with perfect equality (hairy when dealing with floating point numbers) you could simply use the numbers as keys of a hash table & use that to count occurances, looking for one where you have a duplicate.

Since we've defined 'equality' as allowing for some fuziness, the simplest solution would be to sort the array (or a copy) and loop through it until you find an adjacent pair that are "equal".

share|improve this answer
    
Or use only the bits of the exponent and the base up to a certain precision as the hash value into a table rounded up and a table rounded down. It's not the easiest way though. –  Dibbeke Feb 20 '13 at 22:06
add comment

Simplest would probably be to iterate across the inputs and build a sorted list. You can use a binary search on the list, which will either find the duplicate or at least point you to the place where your new number should be inserted. Keep adding the numbers until you find the duplicate. This should be more efficient than sorting the entire input set and searching it (since you should only have to process half the elements, on average), although if you use the system sort routine the code will certainly be simpler.

share|improve this answer
add comment

I would say the simplest algorithm would be to sort the array. Then iterate the array from array[0] --> array[N-2] and at each element array[n] compare against array[n+1] to see if the different falls within the acceptable range.

share|improve this answer
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.