Single Number II

Solving tips

Reason one bit column at a time: numbers appearing 3x contribute 0 or 3 ones to a column, so column_sum % 3 gives exactly the lone number's bit at that position.
Sum the ones at each of 32 positions, take mod 3, and reassemble, O(32n)=O(n) time, O(1) space.
Handle the sign bit: if bit 31 survives, the answer is negative, so subtract 2^31 (Python ints are arbitrary precision and won't do this for you).
Slicker single pass: the ones/twos state machine (ones = (ones ^ num) & ~twos; twos = (twos ^ num) & ~ones) cycles each bit 0->1->2->0; order matters, update ones before twos.

Problem

You are given an integer array nums in which every element appears exactly three times, except for one element that appears exactly once. Return that single element.

You must do it in linear time and using only constant extra space — no hash map of counts, no extra array proportional to the input.

Examples

nums = [2, 2, 3, 2] → 3 2 appears three times; 3 is the lone element.
nums = [0, 1, 0, 1, 0, 1, 99] → 99 0 and 1 each appear three times; 99 appears once.
nums = [-2, -2, 1, 1, -2, 1, 5] → 5 Negatives are allowed; -2 and 1 each appear three times, 5 is alone.

Constraints

1 <= nums.length <= 3 * 10^4
-2^31 <= nums[i] <= 2^31 - 1 (values can be negative; assume 32-bit integers).
Every element appears exactly three times except one, which appears exactly once — the input is guaranteed to have this shape.
Target complexity: O(n) time, O(1) space.

Think about it first

Hint 1

The easy O(n)-space answer is a frequency count — a hash map, or sum-of-unique tricks. The real challenge is dropping to O(1) space. Stop thinking about the numbers as whole values and think about them one *bit* at a time.

Hint 2

Look at a single bit position across the whole array. Every number that appears three times contributes that bit either 0 or 3 times. The lone number contributes it 0 or 1 more. So the total count of 1s at that position is `3k` or `3k + 1` — its value mod 3 reveals the lone number's bit.

Hint 3

Sum the 1-bits at each of the 32 positions, take each sum mod 3, and reassemble — that's O(32n) = O(n) time, O(1) space. Careful with the sign bit (position 31): a set bit there means the answer is negative. There is also a slicker two-variable "ones/twos" state machine that does it in a single pass.

TL;DR

Count set bits per position mod 3 (or run a two-variable ones/twos state machine) — O(n) time, O(1) space.

Approach 1 — Hash-map count (brute force)

Count how many times each value occurs, then return the one whose count is 1. Correct and obvious, but the count table is extra space proportional to the number of distinct values — it violates the O(1)-space requirement.

from collections import Counter
from typing import List

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        counts = Counter(nums)
        for value, freq in counts.items():
            if freq == 1:
                return value
        return -1   # guaranteed unreachable by the constraints

Complexity: O(n) time, O(n) space. Time is fine; the space is the problem. There is a cute arithmetic variant — (3 * sum(set(nums)) - sum(nums)) // 2 — but building set(nums) is still O(n) space, so it dodges nothing.

Approach 2 — Count 1-bits per position, mod 3 (the bit-level insight)

The insight — reason one bit column at a time. Line the numbers up in binary and look down a single column, say bit position i. Every value that appears three times puts the same bit in that column three times, so it contributes either 0 or 3 to the column’s total of 1s. The lone value contributes one extra 0 or 1. Therefore

(number of 1s in column i)  =  3 * (something)         if the lone number's bit i is 0
                            =  3 * (something) + 1      if the lone number's bit i is 1

so column_sum % 3 is exactly the lone number’s bit at position i. Do this for all 32 columns and reassemble the answer bit by bit. Concretely, with nums = [2, 2, 3, 2] (2 = 010, 3 = 011):

        bit2 bit1 bit0
  2  =    0    1    0
  2  =    0    1    0
  3  =    0    1    1
  2  =    0    1    0
 sum:     0    4    1
 %3 :     0    1    1   ->  011 = 3   <- the answer

The one subtlety is the sign bit. In 32-bit two’s complement, bit 31 carries weight -2^31, not +2^31. Python ints are arbitrary precision, so if bit 31 of the answer is set we must subtract 2^31 explicitly to land on the correct negative value.

from typing import List

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        result = 0
        for i in range(32):
            column_sum = 0
            for num in nums:
                column_sum += (num >> i) & 1     # is bit i set in this number?
            bit = column_sum % 3                 # the lone number's bit i
            if i == 31 and bit:                  # sign bit set -> negative
                result -= (1 << 31)
            else:
                result |= (bit << i)
        return result

Walkthrough on nums = [0, 1, 0, 1, 0, 1, 99] (expect 99 = 1100011):

Bit 0: values with bit0 set are 1,1,1,99 → sum 4, 4 % 3 = 1. Set bit 0.
Bit 1: only 99 has bit1 set → sum 1, % 3 = 1. Set bit 1.
Bits 2,3,4: 99’s bits there are 0; the three 1s already cleared → each sum 0. Skip.
Bit 5 (32) and bit 6 (64): 99 = 64 + 32 + 2 + 1, so each has sum 1, % 3 = 1. Set both.
Bits 7..31: sum 0. Result = 1 + 2 + 32 + 64 = 99. ✓

Complexity: O(32 · n) = O(n) time, O(1) space. Works unchanged for negatives thanks to the sign-bit handling.

Approach 3 — `ones`/`twos` state machine (single pass)

The insight: we want a per-bit counter that counts 0 → 1 → 2 → 0 (mod 3) and only ever needs to remember two states, which two bitmasks can encode in parallel across all 32 positions. ones holds the bits that have been seen 1 (mod 3) times; twos holds the bits seen 2 (mod 3) times. On each new number:

a bit enters ones if it is in the incoming number and not currently in twos (going 0 → 1 or 2 → 0 for that bit, handled together);
then twos is updated symmetrically using the freshly computed ones.

When a bit reaches its third occurrence, both masks clear it, so after processing everything the value that appeared once survives in ones.

from typing import List

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        ones, twos = 0, 0
        for num in nums:
            ones = (ones ^ num) & ~twos
            twos = (twos ^ num) & ~ones
        return ones

Walkthrough on nums = [2, 2, 3, 2] (expect 3):

step	num	ones	twos
init	–	000	000
1	010	010	000
2	010	000	010
3	011	001	010
4	010	001	000

After the last step ones = 001 = 3. ✓ (In Python this returns the correct negative for answers with the sign bit set too, because ~ and ^ operate on the same arbitrary-precision two’s-complement representation on both sides.)

Complexity: O(n) time, O(1) space — a single pass with two integer accumulators.

Common pitfalls

Ignoring the sign bit in Approach 2. Without the i == 31 special case, a negative answer comes back as a large positive number (e.g. 2^31 - something). Subtract 2^31 when bit 31 survives.
Only fixing 32 bits when the language has wider ints. Loop exactly range(32) for the stated 32-bit constraint; looping range(64) on a genuinely 32-bit input would misread the sign.
Order matters in the state machine. ones must be updated before twos (and twos uses the new ones). Swapping the two lines breaks the mod-3 cycle.
Reaching for XOR alone. Plain XOR solves Single Number I (elements twice + one once) because pairs cancel. With triples, XOR does not cancel — you need the mod-3 counting above.

Pattern takeaway

When duplicates come in a fixed multiplicity k and you need O(1) space, count contributions per bit position mod k: each bit column sums to a multiple of k plus the lone element’s bit. The generalization to remember: k = 2 collapses to a single XOR; for k = 3 (or any k) either sum-columns-mod-k directly, or build a small bitmask state machine that cycles 0 → 1 → … → k-1 → 0.