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.

There are numbers 1 to N present in a list, and an additional number that has been included by mistake. So, in total there are N+1 numbers. Assume that the largest integer that the language can handle is N. What is the fastest algorithm to find the repeat digit?

Note: This is not a homework problem.

share|improve this question
    
Is this an assignment from school/college? –  ChrisF Jun 7 '11 at 7:58
    
No it is not. Sorry if it appears that way, it was a problem one of my pals gave me as a quiz. He suggested an answer that does not make sense to me. (I am not a CS student) –  picakhu Jun 7 '11 at 7:59
    
That's fair enough, but you might want to make that clear in the question. –  ChrisF Jun 7 '11 at 8:00

1 Answer 1

up vote 5 down vote accepted

I would xor all of the numbers, and xor that with what the xor of the full list should have been. (That xor depends on N and is not hard to figure out.)

This works because xor has the following properties:

  • commutative: a xor b = b xor a
  • associative: (a xor b) xor c = a xor (b xor c)
  • 0 is the identity: a xor 0 = a
  • self-negating: `a xor a = 0

Better yet, it does it without ever changing how many bits you have in your representation. And xor happens to be one of the fastest operations in a computer.

Therefore the result of that computation is the same as you would get if you paired each number in the list with a copy of itself, xored them all together, then the extra number that was inserted by mistke. But that turns into 0 xored with itself a bunch of times then xored with the extra number. Which all becomes just the extra number.

share|improve this answer
    
Thanks, that was his answer too. But I think you did a great job in explaining it. My only question is, how is xor implemented in the compiler? Does the process of xor ever go over the limit of N? –  picakhu Jun 7 '11 at 8:18
    
@picakhu: xor is a basic operation implemented directly in the CPU. See en.wikipedia.org/wiki/Logic_gate for more details. As for the limit, that is tricky. In theory if your maximum integer was 25, you could go over after 24 xor 5. In practice the maximum integer tends to be of the form 2**k-1, and you can't go over. In any case the xor operation doesn't know or care about integers, and so should wind up OK even if it was temporarily too big. –  btilly Jun 7 '11 at 8:28
    
Thanks. I think I figured out how it works. That was very helpful. –  picakhu Jun 7 '11 at 8:30

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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