4 ms·
I just looked at this for 30 seconds, do you just XOR everything together? Then you could XOR it with all the numbers 1 to n again to get just the duplicate num
by robbie-c 4y ago
I just looked at this for 30 seconds, do you just XOR everything together? Then you could XOR it with all the numbers 1 to n again to get just the duplicate number, as every number would appear in the XOR twice except the duplicate number which would appear once.
Edit: I misread the problem :D I initially read it as every number appears once and one number appears twice, but alas it's not so simple :D
- sanedigital 4y agoSum the input list, sum the list of [1...n], subtract and voila!
- robbie-c 4y agoYeah, sadly you're not guaranteed some of the things that are needed for this to work. I defo believe the story that it took Knuth a day to figure this out, although when you see the answer it's pretty easy to understand.
- deleted 4y ago[deleted]
- sanedigital 4y agoWhat things? I submitted it as an answer on Leetcode and it was accepted.