Single Number II
Medium· bit counting· XOR
Problem
In an integer array every value appears exactly three times except one, which appears once. Return that value in linear time with constant extra space.
Examples
Input: nums = [2,2,3,2]
Output: 3
Input: nums = [0,1,0,1,0,1,99]
Output: 99
Constraints
- • 1 <= nums.length <= 3·10^4
- • Every element except one appears three times
Hints & approach
Hint 1
XOR alone no longer cancels things out.
Hint 2
Look at each bit position separately: count how many numbers have it set, modulo 3.
Hint 3
Two masks, "seen once" and "seen twice", can track that count for all bits at once.
Approachtry the hints first
For any bit position, the count of numbers with that bit set is a multiple of 3 plus the lone number's bit. You can sum each of the 32 positions modulo 3, or do it in parallel with two masks: ones = (ones ^ x) & ~twos and twos = (twos ^ x) & ~ones. After processing all numbers, ones holds exactly the bits seen once mod 3, which is the answer.
Time O(n) · Space O(1)