This problem requires finding a single number in an array where every other number appears exactly twice. The solution must have linear time complexity and constant extra space. We can leverage the XOR operation to achieve this efficiently.

The XOR operation (exclusive OR) has a key property: a number XORed with itself results in 0, and a number XORed with 0 results in the number itself. This property allows us to cancel out pairs of numbers that appear twice, leaving only the single number.

Intuition:

Imagine each number as a light switch. If a number appears twice, it's like flipping the switch on and then off, returning it to its initial state. The single number only flips the switch once, leaving it in a different state, allowing us to isolate it.

The XOR operation can be seen as a series of bitwise comparisons. If the bits are the same, the result is 0; otherwise, it's 1. When XORing a number with itself, all bits will be the same, resulting in 0. When XORing with 0, the bits remain unchanged, effectively preserving the other number.

Step-by-step thinking:

Initialize a variable `result` to 0. This variable will accumulate the XOR of all numbers in the array.
Iterate through the input array `nums`.
For each number `num` in the array, perform the XOR operation `result = result ^ num`. This XORs the current value of `result` with the current number.
After iterating through all the numbers, the `result` variable will hold the single number that appears only once. This is because all the duplicate numbers will have canceled each other out due to the XOR property.
Return the final `result`. This is the single number we were searching for.

Time Complexity: O(n)
Space Complexity: O(1)

47. XOR Trick

Understand Before Coding

Visualize This Problem

Draw Your Approach

Example 1:

Example 2:

Example 3:

Constraints:

Learn

Topics

Hint

Use Cases