DSA problem
Single Number II
Given an integer array nums where every element appears exactly three times except for one element which appears exactly once, find and return the single element.
You must design an algorithm that runs in linear time and uses only constant extra space.
The classic XOR trick used for the "appears twice" version does not work here because three copies of a value do not cancel out. Instead, consider each of the 32 bit positions independently. If you sum the bit at a fixed position across all numbers, every value that appears three times contributes a multiple of three. Therefore, taking that sum modulo three leaves only the contribution of the unique number.
Reconstructing the answer one bit at a time from these mod-three counts yields the single element. A more elegant constant-space variant uses two bitmask accumulators that together track each bit count modulo three.
Examples
nums = [2,2,3,2]3nums = [0,1,0,1,0,1,99]99Constraints
- 1 <= nums.length <= 3 * 10^4
- -2^31 <= nums[i] <= 2^31 - 1
- Each element in nums appears exactly three times except for one element which appears exactly once.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.