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

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Examples:

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

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

Solution

Approach: XOR Bitwise Operation

The key idea here is to leverage the properties of the XOR (exclusive OR) bitwise operation.

  • XOR Properties:

    • a ^ 0 = a: Any number XORed with zero is the number itself.
    • a ^ a = 0: Any number XORed with itself is zero.
    • Commutative and Associative: a ^ b ^ c = a ^ (b ^ c) = (a ^ b) ^ c. This means the order of XOR operations doesn't matter.

  • Algorithm:

    1. Initialize a variable, say single_number, to 0.
    2. Iterate through each num in the given array.
    3. For each num, update single_number by single_number = single_number ^ num.
    4. After iterating through all elements, single_number will hold the value of the unique element.

  • Why it works:

    • When a number appears twice, say x and x, their contribution to the XOR sum is x ^ x = 0.
    • Since all other numbers appear twice, their XOR sum effectively becomes 0.
    • Therefore, 0 ^ unique_number = unique_number is what remains.

Time Complexity: O(N) because we iterate through the array once. Space Complexity: O(1) because we use a single variable for the XOR sum.

class Solution:
    def singleNumber(self, nums: list[int]) -> int:
        single_number = 0
        for num in nums:
            single_number ^= num
        return single_number

# Example Usage:
# sol = Solution()
# print(sol.singleNumber([2,2,1])) # Output: 1
# print(sol.singleNumber([4,1,2,1,2])) # Output: 4