Tell me more ×
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.
up vote 0 down vote favorite

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 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 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 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 at 20:14
2  
Is this homework? – Jimmy Hoffa Feb 20 at 20:35

closed as too localized by GlenH7, Glenn Nelson, Martijn Pieters, gnat, ElYusubov Feb 20 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, see the FAQ.

3 Answers

up vote 4 down vote

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 at 22:06
up vote 1 down vote

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
up vote 1 down vote

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

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