Question

An array of n elements contains elements 1-(n-1) in random order and 1 entry is duplicated.

What is the best way to find that duplicate?

Answer 1

would it be to sort and do a linear search? Or to create a new array and compare the two?

Answer 2

If you use a recursion based bubble sort, you could put global variable in there that is set to the value of the item in question. I would suggest that you could use something similar to mark the array index spot, updating as the sort continues. I can't say I've done something like this myself though. This is speculation.

Answer 3

Doing a sort would be a good idea. Normal comparison functions would return -1 for less than, 0 for equal & +1 for greater than. When you get the element that returns 0, you could just return it out of the sort function. Bubble sort is O(n**2), so unless you know n will be small (<32), it's not the best choice.

Answer 4

Bucket sort with n-1 buckets. The bucket with 2 items is the duplicate.