#137 Single Number II
the problem
In plain words
Every element appears exactly three times except one, which appears once. Find it with linear time and constant extra space.
in nums = [2,2,3,2]
out 3
in nums = [0,1,0,1,0,1,99]
out 99
- 1 ≤ nums.length ≤ 3·10⁴
- −2³¹ ≤ nums[i] ≤ 2³¹ − 1
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternBit tricks (shift, mask, lowest set bit)
Look at one bit position at a time. Values that appear three times add 0 or 3 to that column's count. Only the single value can leave a remainder of 1 mod 3.
solutions
From brute force to optimal
Count every value, return the one with count 1.
count.merge(num, 1, Integer::sum)for all nums.- Return the key with value 1.
One pass plus one scan of the map.
About n/3 distinct keys.
class Solution { public int singleNumber(int[] nums) { Map<Integer, Integer> count = new HashMap<>(); for (int num : nums) count.merge(num, 1, Integer::sum); for (Map.Entry<Integer, Integer> e : count.entrySet()) { if (e.getValue() == 1) return e.getKey(); } return -1; // guaranteed not to happen }}For each of the 32 positions, count how many numbers have that bit; a remainder of 1 means the answer has it.
- For bit in 0..31: ones = Σ (num >>> bit) & 1.
- If ones % 3 ≠ 0, set that bit in result.
32 passes over the array.
A couple of ints.
class Solution { public int singleNumber(int[] nums) { int result = 0; for (int bit = 0; bit < 32; bit++) { int ones = 0; for (int num : nums) ones += (num >>> bit) & 1; if (ones % 3 != 0) result |= 1 << bit; // triples add 0 mod 3; the single adds 1 } return result; }}Keep the count mod 3 of every column at once, in two ints: ones holds the bits seen once and twos the bits seen twice.
- ones = (ones ^ num) & ~twos (add num to the "seen once" bits, unless already seen twice).
- twos = (twos ^ num) & ~ones (move bits to "seen twice", or clear on the third time).
- After all nums, ones holds the answer.
One pass, six bitwise operators (two ^, two &, two ~) per element.
Two ints.
class Solution { public int singleNumber(int[] nums) { int ones = 0, twos = 0; // bits seen once / twice (mod 3) for (int num : nums) { ones = (ones ^ num) & ~twos; twos = (twos ^ num) & ~ones; } return ones; }}in the room
How to say it in the interview
talk track
- Lead with the bit-column counting. It is easy to justify, and it is already O(n) time and O(1) space.
- Offer the ones/twos version as a single-pass improvement, and explain it as a per-bit counter going 0 → 1 → 2 → 0.
traps
- Using
>>in the column count. It works here because you mask with& 1, but>>>says what you mean.
what they ask next
Follow-ups
Generalise: every element appears k times except one?
Count each column mod k. The column approach works for any k.
before you submit
Edge cases to test
- A single element.
- The answer is negative (Integer.MIN_VALUE): bit 31 must come out set too.
- Triples of −1 (all 32 bits on) around a positive answer.
practise next
Similar problems
- #136Single NumberEasyin Bits
- #260Single Number IIIMediumin Bits
- #169Majority ElementEasyin Arrays & Strings