227. Find the Element That Appears Once (All Others Appear Exactly Three Times)

Given an array where every element appears exactly three times except for one element that appears exactly once, find that element.

Input: Two lines: the first contains n, the second contains n space-separated integers where every value appears exactly three times except one. Output: Print a single integer - the element that appears exactly once.

1 <= n <= 10^5

This problem is a harder cousin of the 'find the single non-repeating element when everyone else appears twice' pattern (solved by simple XOR) - recognizing WHEN plain XOR breaks down (any repeat count other than an even number) is the real insight being tested.

Almost every number in the list shows up exactly three times - except for one number that shows up only once. Find that one odd-one-out. Brute force: Use a hash map to count occurrences of every distinct value, then scan for the one with count 1 - correct and reasonably efficient, but doesn't showcase (and in interviews, doesn't satisfy the implied challenge of) a pure bit-manipulation, O(1)-extra-space approach. Optimised: Since every REPEATED value contributes a multiple of 3 to each bit position's total count across the whole array, only the unique value can make any bit position's count NOT a multiple of 3 - checking each of the 32 bit positions' count modulo 3 directly reveals exactly which bits belong to the unique element, without ever needing a hash map.

For each element in the array, count how many times it appears by scanning the entire array again (a nested loop comparing every pair of positions). The element whose count comes out to 1 is the answer. This directly implements the problem's definition with no extra memory beyond a counter, but comparing every element against every other element means the work grows quadratically with the array's size. Time: O(n^2) Space: O(1)

Maintain two bitmasks, 'ones' and 'twos', representing bits that have appeared exactly once or exactly twice (mod 3) among the numbers processed so far, updating both with careful bitwise formulas as each number is XORed in and any bit that would reach a third occurrence is cleared from both masks. After processing every number, 'ones' holds exactly the bits of the element that appears only once, since every other element's bits always return to the 'cleared' state after appearing a multiple of three times. This finds the answer in a single pass using only a couple of integer variables, with no hash map or counting array needed at all. Time: O(n) Space: O(1)

Use a hash map to count the occurrences of every distinct value with a single pass over the array, then do a second pass over the map's entries to find the one value with count exactly 1. This replaces the repeated re-scanning of the brute-force approach with a single counting pass followed by a lookup, at the cost of memory proportional to the number of distinct values. Time: O(n) Space: O(n)

1. For each of the 32 individual bit positions (since numbers are stored as 32-bit values), count how many numbers in the array have that specific bit turned on. 2. If every number appeared exactly 3 times, that bit-position count would always be a multiple of 3 - UNLESS the unique number also has that bit set, which throws the count off by exactly one. 3. For each bit position, take the count modulo 3 - a non-zero remainder means the unique element has that bit set. 4. Reconstruct the unique element by combining all the bit positions where the remainder was non-zero.

Time: Proportional to 32 times n (32 bit positions, each requiring one full pass over the array) - effectively O(n), since 32 is a small constant. Space: O(1) - only a small fixed array of 32 bit-position counters, regardless of how many numbers are in the input.

Test n = 1 (only the unique element is present) and n as large as 10^5 to confirm the bitwise-counting approach scales, since a triple-counting hash approach may be too slow or memory-heavy.

This is a well-known, frequently asked bit-manipulation interview problem specifically BECAUSE the simple XOR trick (which solves the 'everyone appears twice except one' variant) doesn't work here - be ready to explain precisely why XOR alone fails for the 'appears three times' variant, and why per-bit counting modulo 3 is needed instead.