Sequence Problem

[iago]

My turn!

My friend posed a problem at me yesterday (and gave me the solution, thankfully ). I figured I'd post it here and see if others come to the same solution.

You have a list of numbers from 1 to n. Exactly one of the numbers is repeated once, and the rest of the numbers are present. The list is not in order. What is the best way to determine which number is repeated?

(Note: sorting the list then doing a search is O(nlog(n)), which is not the best solution)

(Hint: you only have to go over the list once, so the best solution is O(n)).

[rabbit]

Reorder the list as you go along, putting high values at the end and low values at the beginning.  When it's done, the number that occurs twice will be next to itself.

IE:
1. akfhgidecgjb
2. afhgidecgjbk
3. ahgidecgjbfk
4. agidecgjbfhk
5. aidecgjbfghk
6. adecgjbfghik
...
10
10. acdegjbfghik
11. acdegbfghijk
12. abcdegfghijk
13. abcdefgghijk

It required n+1 steps, but that's pretty close (even though I think it's the wrong answer).  I'm not sure if it would be n+1 for ANY n, but eh?

[Sidoh]

What you're doing is essentially sorting and then searching.  I don't think its fair to say "put things in order as you go along," since all you're doing when you're "going along" is sorting.

Also, n+1 steps is still O(n).

[rabbit]

hah

You're right.  It's been a while since I've used/learned orders.

Anyway, I think the algorithm for moving each letter isn't O(n), so it doesn't really matter........

[Sidoh]

Yeah, that's correct.  Moving a letter is constant time, but finding where to put it isn't.

[Rule]

(Edit): I had a solution for log₂n time, but I realised I hadn't read the problem carefully enough.

[iago]

I guess I'll give a hint: the formula for the sum of 1..n is n(n+1)/2.

[rabbit]

Sum all the numbers and subtract the sum of the numbers 1..n with no repeats.

[iago]

Exactly.

Now, what happens if the size of n approaches INT_MAX? How do you solve this without summing the numbers?

(hint: uses XOR)