Single Number II
Medium · Bit Manipulation · Array · Bit Manipulation
Problem
In the integer array nums, every value appears exactly three times except one value, which appears exactly once. Return that value.
Aim for linear time and constant extra space.
Examples
Input: nums = [5,5,-1,5] Output: -1
5 appears three times and -1 once.
Input: nums = [9,1,9,1,9,1,4] Output: 4
9 and 1 each appear three times, leaving 4.
Input: nums = [7] Output: 7
Nothing repeats; 7 is the single value.
Constraints
- 1 <= nums.length <= 3 · 10^4
- -2^31 <= nums[i] <= 2^31 - 1
- exactly one value appears once; every other value appears exactly three times
Approaches
- Baseline: count with a hash map — time O(n), space O(n)
Follow-up
Counting each of the 32 bits separately and keeping count % 3 also works in O(32 n). The use cases change the repeat count to any k and ask for the value that appears twice instead of once.
Related problems
Start free on Cariara · Coding problems · System design studio
