Single Value Among Triples
Problem
In a list of non-negative whole numbers, every value appears exactly three times except one, which appears once. Find that lone value. Aim for constant extra space, so building a tally of every distinct value is off the table.
Examples
Input: nums = [2, 2, 3, 2]
Output: 3Input: nums = [30, 1, 1, 1, 30, 30, 7]
Output: 7
Why: the repeats do not have to sit togetherInput: nums = [5]
Output: 5
Why: edge case, a single value is trivially the lone oneHints
0 / 3
Pairing values off and cancelling them does not work here, because three copies do not cancel the way two copies would.
Stop looking at the values as wholes and look at one binary digit position at a time, across the whole list.
For each of the 32 digit positions, count how many values have a one there. Every tripled value contributes either zero or three to that count, so the remainder after dividing the count by three is the lone value's digit at that position. Reassemble those digits into the answer.
Solution
Looking at a single binary position across the whole list, each tripled value contributes either three ones or none, so the count at that position is a multiple of three plus the lone value's own digit. Taking the count modulo three therefore recovers that digit exactly, and doing this for all 32 positions rebuilds the value. Only a fixed set of counters is ever held, which is what keeps the space constant. Time is O(32n), which is linear, and space is O(1).
def lone_value(nums):
answer = 0
for position in range(32):
# how many values carry a one at this binary position
ones = sum((x >> position) & 1 for x in nums)
if ones % 3: # the triples contribute 0 or 3, never 1 or 2
answer |= 1 << position
return answer
print(lone_value([2, 2, 3, 2])) # -> 3
print(lone_value([30, 1, 1, 1, 30, 30, 7])) # -> 7
print(lone_value([5])) # -> 5Stuck on the idea rather than the code? XOR Tricks covers it.