Single Number easy

Problem Statement

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

You must implement a solution with a linear runtime complexity and use only constant extra space.

Example 1:

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

Example 2:

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

Steps

The core idea is to leverage the bitwise XOR operator (^). The XOR operator has the following properties:

  • Commutative: a ^ b == b ^ a
  • Associative: a ^ (b ^ c) == (a ^ b) ^ c
  • Identity element: a ^ 0 == a
  • Inverse element: a ^ a == 0

Because of these properties, XORing all numbers in the array will cancel out pairs of identical numbers, leaving only the single number.

Explanation

Let's trace Example 2 ([4,1,2,1,2]) step by step:

  1. Start with a variable result initialized to 0.
  2. XOR result with the first element (4): result = 0 ^ 4 = 4
  3. XOR result with the second element (1): result = 4 ^ 1 = 5
  4. XOR result with the third element (2): result = 5 ^ 2 = 7
  5. XOR result with the fourth element (1): result = 7 ^ 1 = 6
  6. XOR result with the fifth element (2): result = 6 ^ 2 = 4

The final result is 4, which is the single number.

Code

def singleNumber(nums):
    """
    Finds the single number that appears only once in an array.

    Args:
        nums: A list of integers.

    Returns:
        The integer that appears only once.
    """
    result = 0
    for num in nums:
        result ^= num
    return result

Complexity

  • Time Complexity: O(n), where n is the length of the input array. We iterate through the array once.
  • Space Complexity: O(1). We use only a constant amount of extra space to store the result variable.

This solution efficiently solves the problem by cleverly utilizing the properties of the bitwise XOR operator, meeting the requirements of linear time and constant space complexity.