{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Single Number – Solution & Complexity

Interview solutions
/
Single Number

Solution Walkthrough

  1. Step 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. Step 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. Step 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. Step 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. Step 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)Missing Number solution (easy)Single Number II solution (medium)Subsets solution (medium)3Sum solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?