136. Single Number

Finding a unique element in an array is a classic interview problem that tests your understanding of bit manipulation and space optimization. This problem frequently appears in technical interviews at companies like Google, Amazon, and Microsoft, where interviewers assess whether you can recognize when bitwise operations eliminate the need for additional memory.

Problem statement

Given an array of integers where every element appears exactly twice except for one element that appears only once, find and return that single element. Your solution must run in linear time complexity and use only constant extra space.

Constraints:

• 1 ≤ nums.length ≤ 3 × 10⁴
• -3 × 10⁴ ≤ nums[i] ≤ 3 × 10⁴
• Each element in the array appears twice except for exactly one element which appears only once.

Examples

Why counting duplicates is inefficient

A straightforward idea is to check each number and count how many times it appears in the array. That means for every element, we scan the entire array to see if it has a pair or not.

This does work logically, but it repeats the same counting work again and again, which becomes expensive as the array grows.

The naive counting approach does repeated scans over the same elements, so the time complexity is o(n^2) in the worst case, with o(1) extra space. With nums.length up to 3 * 10^4, o(n^2) can be roughly 9 * 10^8 comparisons, which is not realistic for interview constraints.

A hash map frequency count improves time to o(n), but it uses o(n) extra space, which violates the constant-space requirement.

Optimized approach using bit manipulation

To meet both constraints, we need a method where duplicates eliminate each other without storing counts.

XOR does exactly that:

• a ^ a = 0
• a ^ 0 = a
• XOR is associative and commutative, so order does not matter.

So if we XOR all numbers together, every pair cancels to 0, and the only thing left is the number that does not have a matching duplicate.

This still works with negatives because XOR operates on the binary representation of integers. In Python, integers have arbitrary precision, but XOR is still consistent and cancellation still holds because the same value XORed with itself always becomes 0.

Common approaches fail here because sorting takes o(n log n) time and a set or dictionary takes o(n) extra space. XOR keeps a single running accumulator, so we stay at o(1) space.

Step-by-step algorithm

1. Initialize a variable result to 0. This will serve as our accumulator for the XOR operations.
2. Iterate through each element num in the input array nums. For each element num:
   1. Compute result = result ^ num (XOR the current element with the accumulated result).
3. After processing all elements, the result variable will contain the single number that appears only once.
4. Return the result as the final answer.

1 / 8

Code implementation

def single_number(nums):
    """
    Find the single number in an array where every other element appears twice.
    
    Args:
        nums: List of integers where all elements appear twice except one
        
    Returns:
        The single integer that appears only once
    """
    # Initialize result to 0 (identity for XOR)
    result = 0
    
    # XOR all elements together
    # Pairs will cancel out (x ^ x = 0)
    # Single element will remain (0 ^ x = x)
    for num in nums:
        result ^= num
    
    return result


def main():
    """Test the single_number function with diverse test cases."""
    
    test_cases = [
        # Test case 1: Single element at the end
        [4, 1, 2, 1, 2],
        
        # Test case 2: Array with only one element
        [7],
        
        # Test case 3: Single element in the middle
        [5, 9, 5, 3, 9],
        
        # Test case 4: Negative numbers
        [-1, -1, -5, 2, 2],
        
        # Test case 5: Larger array with single element at start
        [100, 1, 2, 3, 1, 2, 3]
    ]
    
    for i, nums in enumerate(test_cases, 1):
        result = single_number(nums)
        # print(f"\nTest Case {i}:")
        print(f"{i}.\tInput:  {nums}")
        print(f"\tOutput: {result}")
        print("-"*75)
    

if __name__ == "__main__":
    main()

Time complexity

The time complexity of this algorithm is O(n), where n represents the number of elements in the input array. We traverse the array exactly once, performing a constant-time XOR operation for each element. Since XOR is a bitwise operation that executes in O(1) time regardless of the magnitude of the numbers involved, the total time is directly proportional to the array size. There are no nested loops, recursion, or additional passes through the data, making this a truly linear solution.

Space complexity

The space complexity is O(1), meaning we use constant extra space. Regardless of the input size, we only maintain a single integer variable result to store the running XOR value. We don’t allocate any data structures that grow with the input size, such as hash maps, sets, or additional arrays. The space used remains constant whether the input array contains 10 elements or 10,000 elements, which satisfies the problem’s strict space constraint.

Common pitfalls and interview tips

1. Forgetting the XOR identity properties: Many candidates know about XOR but forget that x ⊕ x = 0 and x ⊕ 0 = x. These properties are the foundation of this solution. During an interview, explicitly state these properties when explaining your approach to demonstrate deep understanding of bitwise operations.
2. Attempting to use sum-based approaches without considering edge cases: Some candidates try to calculate 2 × (sum of unique elements) - (sum of all elements). While this mathematically works, it’s prone to integer overflow with large numbers and becomes complicated with negative values. The XOR approach avoids these pitfalls entirely and is more elegant.
3. Not considering the commutative nature of XOR: A common mistake is thinking that the order of elements matters or that we need to pair elements before XORing. Remember that XOR is both commutative and associative, so a ^ b ^ c equals c ^ a ^ b equals b ^ c ^ a. This property allows us to process elements in any order without sorting.