Single Number
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Every number appears twice except one that appears once. Find that one using constant extra space.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1What happens when you XOR a number with itself?
- Hint 2Does the order of XORing matter?
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
A light switch: pressing it twice leaves the light exactly as it was. Give every number its own switch. Go through the list pressing the switch of each number. Numbers that appear twice are pressed twice and end up off again. The only switch left on belongs to the number that appeared once. XOR is that switch applied to all the bits at once.
- The obvious way
Count with a dictionary: O(n) time but O(n) space. Sorting: O(n log n).
- The key insight
Start with result = 0 and XOR every number into it. Each pair cancels (x XOR x = 0), and XOR with 0 changes nothing, so the number that appears once is left.
- The algorithm
- result = 0.
- For each number: result = result XOR number.
- Pairs cancel themselves.
- Return result.
Watch it run
Examplenums = [4, 1, 2, 1, 2]
Press switch 4: it is now on. Switch 1: on. Switch 2: on.
on: 4, 1, 2
Where people slip
- This trick needs every other number to appear an EVEN number of times (here exactly twice).
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def single_number(nums):
result = 0
for number in nums:
result ^= number # pressing the same switch twice cancels out
return resultNow close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.