Single Number - Solution & Explanation

Problem Overview: You receive an integer array where every element appears exactly twice except for one element that appears only once. The task is to find that single element. The solution must work efficiently even when the array grows large.

Approach 1: Hash Map Counting (O(n) time, O(n) space)

This approach uses a frequency map to count how many times each number appears. Iterate through the array and store counts using a hash map where the key is the number and the value is its frequency. After building the map, scan through the entries and return the number with frequency 1. The logic is straightforward and easy to implement, which makes it a good baseline approach when you first reason about the problem. However, it requires extra memory proportional to the number of unique elements.

This technique relies on constant-time hash lookups and works well for many array counting problems. The tradeoff is memory usage since the hash map stores up to n keys.

Approach 2: XOR Operation (O(n) time, O(1) space)

The optimal solution uses properties of the XOR bitwise operator. XOR has two useful rules: a ^ a = 0 and a ^ 0 = a. When you XOR all numbers in the array together, duplicate numbers cancel each other out because each pair produces zero. The only value left after the full pass is the number that appears once.

Implementation is simple: initialize a variable result = 0, iterate through the array, and update result ^= num for each element. After processing the entire array, result holds the unique element. The algorithm performs a single pass and uses only one variable for storage, giving constant extra space.

This approach is a classic example of using bit manipulation to reduce memory usage. It avoids auxiliary data structures while maintaining linear runtime, which makes it both elegant and efficient.

Recommended for interviews: Interviewers usually expect the XOR solution. Starting with the hash map approach demonstrates you understand the problem using counting and hash lookups. Moving to the XOR technique shows deeper algorithmic thinking and familiarity with bitwise operations. The XOR solution achieves the optimal O(n) time and O(1) space, which is the key improvement interviewers look for.