Single Number II
Solve this ProblemTest Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ nums.length ≤ 3 × 10⁴ - ◆
-3 × 10⁴ ≤ nums[i] ≤ 3 × 10⁴ - ◆
Every value in nums appears exactly three times, except for one value which appears exactly once
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Hashmap Counting
GoodCount how many times each value occurs, then scan for the one entry whose count is 1. This works regardless of whether the repeated values show up twice, three times, or any other fixed count — but it always costs memory proportional to how many distinct values are in the array.
O(n)O(n)1class Solution {
2 public int singleNumber(int[] nums) {
3 Map<Integer, Integer> freq = new HashMap<>();
4 for (int num : nums) {
5 freq.put(num, freq.getOrDefault(num, 0) + 1);
6 }
7 for (Map.Entry<Integer, Integer> entry : freq.entrySet()) {
8 if (entry.getValue() == 1) {
9 return entry.getKey();
10 }
11 }
12 return -1;
13 }
14}Optimal — Bit Position Counting
OptimalLook at each of the 32 bit positions independently. For every position, add up how many numbers have a 1 there. Since every repeated value contributes that bit exactly three times (or zero times), the total at each position is always a multiple of 3 — except at positions where the single value has a 1 bit, which tips the total to one more than a multiple of 3. Whichever bit positions have a count not divisible by 3 belong to the answer.
O(n)O(1)1class Solution {
2 public int singleNumber(int[] nums) {
3 int result = 0;
4 for (int bit = 0; bit < 32; bit++) {
5 int count = 0;
6 for (int num : nums) {
7 if (((num >> bit) & 1) != 0) {
8 count++;
9 }
10 }
11 if (count % 3 != 0) {
12 result |= (1 << bit);
13 }
14 }
15 return result;
16 }
17}