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

Constraints:

  • The array nums is non-empty.
  • Each element in the array appears twice, except for one element which appears only once.

Example:

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

Another Example:

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

Solution

Approach:

  • XOR Property: The key property of the XOR bitwise operator is that A XOR A = 0 and A XOR 0 = A.
  • If we XOR all the numbers in the array, the pairs of identical numbers will cancel each other out (result in 0).
  • The only number remaining (XORed with 0) will be the single number that appears only once.

Algorithm:

  1. Initialize a variable single_number to 0. This will act as our accumulator for XOR operations.
  2. Iterate through each number num in the input array nums.
  3. For each num, update single_number = single_number XOR num.
  4. After iterating through all numbers, single_number will hold the unique element.
  5. Return single_number.

Example walkthrough nums = [4,1,2,1,2]:

  • single_number = 0
  • single_number = 0 XOR 4 = 4
  • single_number = 4 XOR 1 = 5 (binary: 100 XOR 001 = 101)
  • single_number = 5 XOR 2 = 7 (binary: 101 XOR 010 = 111)
  • single_number = 7 XOR 1 = 6 (binary: 111 XOR 001 = 110)
  • single_number = 6 XOR 2 = 4 (binary: 110 XOR 010 = 100)
  • Result: 4

Code (Python):

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