137. Single Number II
You receive an array of integers nums in which every value appears exactly three times, except for one value that appears exactly once. Return that lone value.
A hash map settles it quickly, but the real prize is a linear-time solution that keeps only constant extra state — and unlike plain XOR, triples don't cancel themselves, so you'll need a sharper bit-level idea.
Example 1:
Input: nums = [7, 7, 4, 7]
Output: 4
Explanation: 7 appears three times; 4 appears once.
Example 2:
Input: nums = [4, 2, 4, 2, 4, 2, 55]
Output: 55
Explanation: 4 and 2 each appear three times, leaving 55 as the loner.
Constraints:
- 1 ≤ nums.length ≤ 3 * 10⁴
- -2³¹ ≤ nums[i] ≤ 2³¹ - 1
- Every value appears exactly three times, except one value that appears exactly once.
Hints:
A hash map of value → count is the warm-up: one pass to tally, one scan to find the count of 1. It costs O(n) extra space.
Fix one bit position k and count how many array values have that bit set. Every tripled value contributes 0 or 3 to the count — so count mod 3 is exactly the loner's bit k. Mind the sign bit for negative numbers.
The per-bit tally can be compressed into two accumulators, ones and twos, holding the bits seen once and twice so far. The update ones = (ones ^ x) & ~twos; twos = (twos ^ x) & ~ones wipes a bit clean the third time it shows up, leaving ones equal to the answer.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [7, 7, 4, 7]
Expected output: 4