{ }DevToolsDaily
ToolsInterview
Problems
New
CheatsheetsChat
New
BlogPricing
Ctrl + K

Single Number – Solution & Complexity

Interview solutions
/
Single Number

1. Understand the Pattern

  • Every value appears exactly twice except one value.
  • We need to return the value that appears once.
  • The challenge asks for linear time and no extra memory.

2. Counting Approach

  • A dictionary can count how many times each number appears.
  • Then we return the number with count 1.
  • This is O(n) time, but it uses O(n) extra space.
def single_number(nums):
    counts = {}
    for num in nums:
        counts[num] = counts.get(num, 0) + 1
    for num, count in counts.items():
        if count == 1:
            return num

3. Key Insight: XOR Cancels Pairs

  • XOR has useful properties: x ^ x = 0 and x ^ 0 = x.
  • XOR is also commutative, so order does not matter.
  • When all numbers are XORed together, paired values cancel and only the single value remains.

4. Accumulate with XOR

  • Start with result = 0.
  • XOR every number into result.
  • After the loop, result is the number that appeared once.
def single_number(nums):
    result = 0
    for num in nums:
        result ^= num
    return result

5. Final Solution and Complexity

  • The XOR solution meets the follow-up requirement.
  • Time complexity is O(n).
  • Space complexity is O(1).
def single_number(nums: list[int]) -> int:
    result = 0
    for num in nums:
        result ^= num
    return result

FAQ

See also:

Practice Single Number online (run code in the browser)Best Time to Buy and Sell Stock solution (easy)Binary Search solution (easy)Coin Change solution (medium)Container With Most Water solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsContact Us © Monkey SkatesHave kids?