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.

Example 1:

Input: [4, 4, 14, 4]
Output: 14

Example 2:

Input: [6, 7, 7, 7, 13, 6, 6]
Output: 13

Constraints:

• 1 <= nums.length <= 10^4
• -1000 <= nums[i] <= 1000
• Every element in nums appears exactly three times except for one element, which appears exactly once.

Verification

Trace [4, 4, 14, 4] by hand at each bit position: 4=0100, 14=1110.

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

Answer = 1110 = 14. Correct.

Solution Breakdown

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 [4, 4, 14, 4] where 4 is 0100 and 14 is 1110. Bit 0: the bits are 0,0,0,0, summing to 0; 0 % 3 = 0, so leave bit 0 clear. Bit 1: the bits are 0,0,1,0, summing to 1; 1 % 3 = 1, so set bit 1. Bits 2 and 3 each sum to 4; 4 % 3 = 1, so set both. The result is binary 1110 = 14, 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 [9] 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.