Single Number

Easy#136xor

You get an array of integers in which every number occurs exactly twice, except one that occurs once. Find that one, in one pass and with O(1) extra memory. Our example: [10, 3, 7, 3, 10] — the answer is 7.

136 Single NumberWalkthrough · 1×

Example: [10, 3, 7, 3, 10]. The rows under the array are num and result in binary; the flipped bits of result light up.

0101327334108421place valuenum—result0000= 0
not reached yet; a 0 bitcurrent number; a bit that just flippedin result, its pair not met yet; a 1 bit of resulta 1 bit of num: it flips resulta pair that cancelled outthe number without a pair

result starts at 0 = 0000, which changes nothing in xor

01/13
restart · back · play · step
Speed
1function singleNumber(nums):
2 result = 0
3 for each num in nums:
4 result = result xor num
5 return result
state
result
0 = 0000
num
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. xor flips each bit of result where num has a 1. A number that comes twice flips the same bits twice, so they end where they started: a xor a = 0, and x xor 0 = x.
  2. Flips do not depend on order: the two 10s are far apart, and in between result passes 9, 14 and 13, numbers that are not in the array. Only the end result counts.
  3. After every number, each bit of result is 1 exactly when an odd number of numbers had a 1 there. The pairs add an even count everywhere, so what is left are the bits of the single number.

Complexity

Time O(n): one pass, one xor per number. Memory O(1): a single number, no set or map.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.