How to find the only number in an array that doesn't occur twice

Several approaches can be used to solve this problem. Here, I will introduce two commonly used methods: one utilizing a hash table and the other employing the XOR operation.

Method One: Using a Hash Table

Using a hash table to track the frequency of each element in the array, then iterating through the hash table to identify the element that appears only once.

Steps:

1. Initialize an empty hash table.
2. Iterate through the array. For each element, if it is not present in the hash table, add it with a count of 1; otherwise, increment its count.
3. Iterate through the hash table again to find the element with a count of 1.

Code Example (Python):

python
def singleNumber(nums):
    count_map = {}
    for num in nums:
        if num in count_map:
            count_map[num] += 1
        else:
            count_map[num] = 1

    for num, count in count_map.items():
        if count == 1:
            return num

Method Two: Using the XOR Operation

The XOR operation has a notable property: XORing any number with 0 yields the number itself, and XORing any number with itself yields 0. Utilizing this property, we can efficiently identify the number that appears only once.

Steps:

1. Initialize a variable result to 0.
2. Iterate through the array, XORing each element with result.
3. Since all numbers except one appear exactly twice, they will cancel each other out.
4. The final value of result will be the number that appears only once.

Code Example (Python):

python
def singleNumber(nums):
    result = 0
    for num in nums:
        result ^= num
    return result

Summary

In terms of time and space efficiency, the XOR approach is more efficient as it has a time complexity of O(n) and a space complexity of O(1). Conversely, the hash table method, while also having a time complexity of O(n), has a space complexity of O(n) due to the additional space required to store the elements and their counts.

The solutions for these two cases differ, but I can outline approaches for both.

Case 1: Finding the number that appears only once, with all other numbers appearing two or more times

If all elements in the array appear in pairs, except for one number that appears only once, a highly efficient solution is to use the XOR operation. The XOR operation has the following properties:

• A number XORed with itself results in 0, i.e., a ^ a = 0.
• A number XORed with 0 results in itself, i.e., a ^ 0 = a.
• The XOR operation is commutative and associative, i.e., a ^ b ^ a = (a ^ a) ^ b = 0 ^ b = b.

Therefore, XORing all elements in the array causes numbers appearing in pairs to cancel each other out to 0, leaving the result as the number that appears only once. This method has a time complexity of O(n) and space complexity of O(1), making it highly efficient.

For example, with the array [4, 1, 2, 1, 2], using XOR:

shell
4 ^ 1 ^ 2 ^ 1 ^ 2 = (1 ^ 1) ^ (2 ^ 2) ^ 4 = 0 ^ 0 ^ 4 = 4

The final result is 4, which is the number that appears only once.

Case 2: Finding the number that appears only once with no restrictions

If the frequency of numbers in the array is unrestricted, the XOR method may not be applicable. In this case, we can use a Hash Table to record the frequency of each number.

The steps are as follows:

1. Traverse the array, storing each element as a key in the hash table with its frequency as the value.
2. Traverse the hash table again to find the key with a value of 1, which is the number that appears only once.

This method has both time and space complexity of O(n). For example, with the array [4, 1, 2, 1, 2, 4, 3], the hash table is built as:

plaintext
{
  1: 2,
  2: 2,
  3: 1,
  4: 2
}

After traversing the hash table, we find that the number 3 has a frequency of 1, so 3 is the number that appears only once.