Introduction

In programming challenges, a common problem is identifying a unique element in an array where every element except one appears multiple times. Suppose we have an array of integers (range from (−2^{31}) to (2^{31}-1)), where each number can repeat “n” times except for one ‘loner’ number.

For this discussion, we assume all numbers appear three times except the loner, for example: [2, 2, 3, 2].

Challenges with Negative Integers

Different programming languages have unique methods for representing negative integers. Assuming negative integers are represented in 2’s complement, the number of bits in a number will be 32.

Solving the Problem

There are several methods to solve this problem:

Sorting the Array

A simple method is to sort the array and iterate to find the loner:

def find_single_number(nums):
    nums.sort()
    for i in range(0, len(nums) - 1, 3):
        if nums[i] != nums[i + 1]:
            return nums[i]
    return nums[-1]  # Handle single number at the end

This method has a time complexity of O(NlogN) due to sorting.

Using a Hash Map

Another approach is using a hash map to count the frequency of each number:

def find_loner_number(nums):
    frequency = {}
    for num in nums:
        frequency[num] = frequency.get(num, 0) + 1
    for num, count in frequency.items():
        if count == 1:
            return num

This approach operates in O(N) space.

Bit Manipulation (Optimal Solution)

The most efficient method uses bit manipulation:

def find_single_number(nums):
    result = 0
    for i in range(32):
        bit_sum = 0
        for num in nums:
            bit_sum += (num >> i) & 1
        result |= ((bit_sum % 3) << i)
    return result

This solution exploits the fact that each number appears three times, and thus, bits at each position also appear three times. Any bit in the result that isn’t zero must belong to the loner number.

Conclusion

Using bit manipulation provides an elegant and efficient solution to this common problem, optimizing both time and space complexity. For variations where numbers repeat ‘n’ times except one, adjust the modulo operation accordingly.

Generalization

To generalize this solution, adjust the repeating frequency n for situations where each number might repeat a different number of times, not just three.