Single Number II

Problem

Fault-tolerant storage systems triplicate every record for redundancy - but a corruption check finds one record that was written only once. Given an integer array where every element appears exactly 3 times except one, find and return the unique element in O(n) time and O(1) space.

Input: [2, 2, 3, 2]          → 3
Input: [0, 1, 0, 1, 0, 1, 99] → 99

Verification

Trace [2, 2, 3, 2] by hand at each bit position: 2=010, 3=011.

• Bit 0: 0+0+1+0=1; 1%3=1 → bit 0 is set in answer
• Bit 1: 1+1+1+1=4; 4%3=1 → bit 1 is set in answer
• Bit 2+: all zeros

Answer = 01 + 10 = 11 = 3. Correct.

Solution

Approach - Per-bit counting modulo 3.

XOR fails here because a ^ a ^ a = a rather than 0, so triples do not cancel. Instead, treat each bit position independently. For every position from 0 to 31, sum that bit across all numbers with sum((num >> bit_position) & 1 for num in nums). Each element that appears three times contributes its bit three times, so every triple adds a multiple of 3 to that position's total. The unique element contributes its bit just once. Therefore, at any position, bit_sum % 3 is non-zero exactly when the unique element has a 1 there - the leftover that the triples could not absorb. Set that bit in the answer with result |= (1 << bit_position) and the answer reassembles bit by bit.

Trace [2, 2, 3, 2] where 2 is 010 and 3 is 011. Bit 0: the bits are 0,0,1,0, summing to 1; 1 % 3 = 1, so set bit 0. Bit 1: the bits are 1,1,1,1, summing to 4; 4 % 3 = 1, so set bit 1. All higher bits sum to 0. The result is binary 11 = 3, the element that appeared once. The condition generalizes: for elements appearing k times except one, swap the test to bit_sum % k.

Edge cases - A single-element array like [7] works because every bit's sum is just that element's bit, never divisible by 3. The 32-position loop assumes non-negative inputs fit in 32 bits; signed negatives would need sign handling.

Complexity - O(32n) = O(n) time, O(1) space - 32 fixed passes over the array, only the result integer retained.