Domain 1EasyCORE

Single Number

The problem asks us to find the single number in an array where every other number appears exactly twice. The input is a non-empty list of integers, and the output should be the integer that appears only once. The constraints include the range of numbers and the fact that all numbers except one appear twice.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Hash Table#Bit Manipulation

136. Single Number

Model: qwen2.5-coder:14b
Topics: Hash Table,Bit Manipulation
FAANG asked: 1
Acceptance rate: 66.7%


Problem Breakdown

The problem asks us to find the single number in an array where every other number appears exactly twice. The input is a non-empty list of integers, and the output should be the integer that appears only once. The constraints include the range of numbers and the fact that all numbers except one appear twice.

Key points:

  • Input: A list of integers nums with length between 1 and 30,000.
  • Output: An integer that appears exactly once in the list.
  • Constraint: All other integers appear exactly twice.
  • Edge cases: The list could contain negative numbers, and the single number could be at any position.

Intuition

A brute-force approach would involve using a hash table to count occurrences of each number. This would work but would require extra memory proportional to the number of unique elements in the array (O(n) space complexity). Additionally, it would have a time complexity of O(n) due to iterating through the list twice.

The key insight is that we can use bitwise XOR operation to solve this problem without extra memory and with linear runtime. The XOR operation has a few useful properties:

  • a ^ a = 0 for any integer a.
  • a ^ 0 = a for any integer a.
  • XOR is commutative and associative, meaning the order of operations does not matter.

Given these properties, if we XOR all numbers in the array together, pairs of identical numbers will cancel each other out (resulting in 0), leaving only the single number that appears once.

Approach

  1. Initialize a variable single to 0.
  2. Iterate through each number in the list nums.
  3. For each number, apply the XOR operation between single and the current number.
  4. After processing all numbers, single will hold the value of the number that appears only once.

Complexity Analysis

  • Time Complexity: O(n), where n is the length of the input list nums. We iterate through the list once.
  • Space Complexity: O(1). We use a constant amount of extra space regardless of the input size.

Solution

def singleNumber(nums):
    single = 0
    for num in nums:
        single ^= num
    return single

Edge Cases Handled

  • Single element list: If the list contains only one element, the algorithm will correctly return that element.
  • Negative numbers: The XOR operation works with negative numbers as well, so the presence of negative numbers does not affect the solution.
  • All elements are the same except one: The algorithm will correctly identify the single different element.

The provided solution is correct and efficient. It meets all the requirements specified in the problem statement, including handling edge cases and maintaining linear time complexity with constant space complexity.