Single Number II

Medium#137bit by bit

You get an array of integers in which every number occurs three times, except one that occurs once. Find that one in linear time and with O(1) extra memory. Our example: [3, 5, 3, 6, 5, 3, 5] — the answer is 6.

137 Single Number IIWalkthrough · 1×

Example: [3, 5, 3, 6, 5, 3, 5], width = 3. Each column under a number is its bits; the right column counts the ones in the bit row.

nums3536535onesbit 20101101bit 11011010bit 01110111answer000= 0
a 0 bita 1 bitthe bit being reada 1 already counted; the count so fara count that is a multiple of 3a bit of the answer; the number without a triple

answer starts at 000: its bits are set one column at a time

01/55
restart · back · play · step
Speed
1function singleNumber(nums, width):
2 answer = 0
3 for b from 0 to width - 1:
4 ones = 0
5 for each num in nums:
6 ones = ones + ((num >> b) & 1)
7 if ones % 3 == 1:
8 answer = answer | (1 << b)
9 return answer
state
answer
0 = 000
b
–
ones
–
num
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. Look at one bit position. Each number that occurs three times puts 0 or 3 ones there, so the triples give a multiple of 3. The single number adds 1 or 0 on top, and ones % 3 tells which.
  2. Bits do not mix: each position is counted on its own, and the positions with ones % 3 = 1 are exactly the 1 bits of the answer. In column 0 the two triples give 6 ones, and 6 % 3 = 0.
  3. Plain xor does not work here: three copies of a number flip its bits three times and leave one copy. Here xor of everything is 0, not 6.

Complexity

Time O(w · n), where w is the width: one pass over the numbers per bit, and w = 32 on LeetCode, so O(n). Memory O(1): the count and the answer.

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.