Single Number II - Solution & Explanation

Problem Overview: You are given an integer array where every element appears exactly three times except for one element that appears once. Your task is to find that unique element while maintaining linear time complexity and minimal extra space.

Approach 1: Use a Map to Count Frequencies (O(n) time, O(n) space)

The most direct solution is counting how many times each value appears. Iterate through the array and store frequencies in a hash map where the key is the number and the value is its count. After building the map, iterate through its entries and return the number whose frequency equals one. Hash map lookup and updates run in constant time on average, so the full traversal stays O(n).

This approach works well when clarity is more important than memory usage. It is easy to implement in any language and clearly reflects the problem statement: count occurrences and pick the unique one. The tradeoff is extra memory proportional to the number of distinct values. Problems involving counting frequencies commonly rely on structures like hash maps and appear frequently with array processing tasks.

Approach 2: Bit Manipulation (O(n) time, O(1) space)

The optimal solution uses bit manipulation. Instead of counting whole numbers, count how many times each bit position is set across all elements. For a 32‑bit integer, iterate through all 32 bit positions. For each position, scan the array and count how many numbers have that bit set. Since every repeated number appears exactly three times, the total count for those bits will always be divisible by three.

Take the count modulo 3 for each bit. If the remainder is 1, that bit belongs to the unique number. Reconstruct the final answer by setting those bits in the result. This works because the contributions from numbers appearing three times cancel out under modulo 3 arithmetic.

This method runs in O(32 × n) time, which simplifies to O(n), and uses constant extra space. It relies heavily on operations like bit shifts, bit masks, and bitwise AND. These techniques are core concepts in bit manipulation problems and often appear when constraints forbid extra memory.

Recommended for interviews: The bit manipulation approach is what most interviewers expect. The frequency map solution demonstrates that you understand the problem and can produce a correct baseline quickly. However, the O(1) space bit counting technique shows deeper understanding of binary representation and optimization. Interviewers often use this problem specifically to test your ability to reason about bits and eliminate repeated patterns using modulo arithmetic.