Every number appears three times except one. Count each of the 32 bits across the array; a count that isn't a multiple of 3 belongs to it.
▼The problem
LeetCode 137 (Medium). Every element of nums appears exactly three times except one, which appears once. Find that single one in O(n) time and O(1) extra space.
Examples (LeetCode's): [2,2,3,2] → 3 (walked through in scene 6) and [0,1,0,1,0,1,99] → 99 (the key idea in scene 4, on seven bit trays: 99 = 1100011).
The solution
def singleNumber(nums):
ans = 0
for b in range(32):
cnt = sum((x >> b) & 1 for x in nums)
if cnt % 3:
ans |= 1 << b
if ans >= 1 << 31: # sign bit
ans -= 1 << 32
return ansTranscript
Single Number Two. Every number in the list appears three times, except one, which appears once. Find it in linear time with constant extra space.
Two, two, three, two: the single one is three. Zero, one, zero, one, zero, one, ninety-nine: it's ninety-nine.
The easy way counts every number in a hash map, but that map grows with the input. Sorting needs no map, but costs n log n. And the XOR trick from Single Number fails: pairs cancel, but three copies XOR back to the number itself.
So count bits instead. Give each bit position a tray. Every number with that bit set drops in a cookie, and the baker boxes cookies in threes. Tripled numbers always fill whole boxes, so the leftover, the count mod three, is the single number's bit.
In code, loop over thirty-two bits, count the ones, and set the bit when the count mod three is one. In Python, if the sign bit is set, subtract two to the thirty-two. Or keep two masks, ones and twos, that count every bit mod three at once. The answer is ones.
Let's walk two, two, three, two. In binary, two is one zero, and three is one one. The twos tray gets four cookies: one box, one left over. The ones tray gets a single cookie, left over. Leftovers one and one: binary three.
Thirty-two passes over n numbers is order n time, and a few counters is order one space.
Count each bit, keep it mod three, rebuild the number. That's Single Number Two.