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

Single Number II – Solution & Complexity

Interview solutions
/
Single Number II

Solution Walkthrough

  1. Step 1: Why plain XOR is not enough

    • XOR cancels values that appear an even number of times.
    • Here duplicates appear three times (odd), so XOR does not cleanly remove them.
    • We need to reason bit by bit instead.

  2. Step 2: Count each bit modulo three

    • For each of the 32 bit positions, count how many numbers have that bit set.
    • Every tripled value contributes a multiple of three, so count % 3 isolates the unique number's bits.
    • Rebuild the answer from the remaining bits (sign-extending the top bit for negatives).
    def single_number(nums):
    result = 0
    for bit in range(32):
        count = 0
        for num in nums:
            count += (num >> bit) & 1
        if count % 3:
            result |= 1 << bit
    if result >= (1 << 31):
        result -= 1 << 32
    return result

  3. Step 3: Constant-space bitmask automaton

    • Track two masks: ones holds bits seen once, twos holds bits seen twice.
    • A bit resets to zero once it has been seen three times.
    • After processing every number, ones is exactly the unique value.

  4. Step 4: Two-mask solution

    • ones = (ones ^ num) & ~twos records bits appearing a first time while clearing any at two.
    • twos = (twos ^ num) & ~ones promotes bits to the two state, clearing any now back at one.
    • This is O(n) time and O(1) space with no per-bit loop.
    def single_number(nums):
    ones = twos = 0
    for num in nums:
        ones = (ones ^ num) & ~twos
        twos = (twos ^ num) & ~ones
    return ones

  5. Step 5: Dry run

    Trace nums = [2, 2, 3, 2] (binary 2 = 10, 3 = 11).

    numonestwos
    start0000
    21000
    20010
    30110
    20100

    Final ones = 01 = 3, the unique value.

  6. Step 6: Final solution and complexity

    The two-mask automaton returns the unique value in O(n) time and O(1) extra space.

    def single_number(nums: list[int]) -> int:
    ones = twos = 0
    for num in nums:
        ones = (ones ^ num) & ~twos
        twos = (twos ^ num) & ~ones
    return ones

FAQ

See also

Practice Single Number II online (run code in the browser)Missing Number solution (easy)Single Number solution (easy)Subsets solution (medium)3Sum solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?