Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

Constraints

  • The array nums will always contain exactly one element that appears only once.
  • Your algorithm should have a linear runtime complexity.
  • Can you implement it without using extra memory (i.e., constant space complexity)?

Examples

Example 1:

Input: nums = [2,2,1]
Output: 1

Example 2:

Input: nums = [4,1,2,1,2]
Output: 4

Solution

The key to solving this problem efficiently is to leverage the properties of the bitwise XOR operation (^).

Approach

  • XOR Properties: The XOR operation has a few crucial properties:
    • a ^ 0 = a (XORing with zero returns the number itself)
    • a ^ a = 0 (XORing a number with itself results in zero)
    • a ^ b ^ a = (a ^ a) ^ b = 0 ^ b = b (XOR is commutative and associative, allowing numbers to cancel each other out)
  • Algorithm:
    1. Initialize a variable, result, to 0. This result will accumulate the XOR of all numbers.
    2. Iterate through each number num in the input array nums.
    3. In each iteration, update result = result ^ num.
  • Why it works: When we XOR all numbers in the array, any number that appears twice will effectively cancel itself out due to a ^ a = 0. Since 0 ^ X = X, the only number left in result at the end will be the single unique number that appeared only once.

Python Code Solution

class Solution:
    def singleNumber(self, nums: list[int]) -> int:
        # Initialize result with 0. XORing any number with 0 yields that number.
        result = 0
        
        # Iterate through all numbers in the array
        for num in nums:
            # XOR the current number with the accumulated result
            # If a number appears twice, it will effectively cancel itself out
            result ^= num
            
        # The remaining value in result is the single number
        return result