Interview Prepbit-manipulationmediumAmazonGoogleFacebook

Single Number III (Two Singles)

Choose your preparation mode4 modes available

Try It Solution Trace

▶

Steps

setup

Initialize xor to 0

We start by initializing the xor variable to 0 before processing any numbers. This variable will accumulate the XOR of all numbers.

💡 Starting with 0 is essential because XOR with 0 leaves the number unchanged, allowing accumulation.

Line:xor = 0

💡 xor starts neutral and will hold the combined XOR of all numbers.

fill_row

XOR with first number 1

XOR the current xor (0) with the first number 1. This updates xor to 1.

💡 XOR with 0 returns the number itself, so xor becomes 1.

Line:xor ^= num # num=1

💡 xor now holds the XOR of numbers processed so far: 1.

fill_row

XOR with second number 2

XOR the current xor (1) with the second number 2. This updates xor to 3 (binary 11).

💡 XOR combines bits where bits differ, accumulating unique bits.

Line:xor ^= num # num=2

💡 xor now holds 3, the XOR of 1 and 2.

fill_row

XOR with third number 1

XOR the current xor (3) with the third number 1. Since 1 appeared before, it cancels out, updating xor to 2.

💡 XORing a number twice cancels it out, leaving only unique bits.

Line:xor ^= num # num=1

💡 xor now holds 2, reflecting cancellation of duplicate 1.

fill_row

XOR with fourth number 3

XOR the current xor (2) with the fourth number 3. This updates xor to 1.

💡 XOR accumulates differences, updating xor to reflect combined unique bits.

Line:xor ^= num # num=3

💡 xor now holds 1, reflecting XOR of processed numbers.

fill_row

XOR with fifth number 2

XOR the current xor (1) with the fifth number 2. This updates xor to 3.

💡 XOR accumulates differences, updating xor to 3.

Line:xor ^= num # num=2

💡 xor now holds 3, the XOR of all numbers processed so far.

fill_row

XOR with sixth number 5

XOR the current xor (3) with the sixth number 5. This updates xor to 6 (binary 110).

💡 Final XOR accumulates all numbers, resulting in XOR of the two unique numbers.

Line:xor ^= num # num=5

💡 xor now holds 6, which is 3 ^ 5, the XOR of the two unique numbers.

compare

Find rightmost set bit in xor

Calculate set_bit = xor & (-xor) to isolate the rightmost set bit in xor (6). This bit differentiates the two unique numbers.

💡 Isolating the rightmost set bit helps partition numbers into two groups.

Line:set_bit = xor & (-xor)

💡 set_bit isolates the lowest bit where the two unique numbers differ.

setup

Initialize num1 and num2 to 0

Initialize num1 and num2 to 0 before partitioning numbers based on set_bit.

💡 These will hold XOR results of two partitions.

Line:

num1 = 0
num2 = 0

💡 Starting fresh to accumulate XORs in each group.

traverse

Partition first number 1 by set_bit and XOR

Check if 1 & set_bit (2) is nonzero. It is zero, so XOR 1 into num2.

💡 Partitioning numbers by set_bit groups duplicates separately.

Line:

if num & set_bit:
    num1 ^= num
else:
    num2 ^= num  # num=1

💡 Numbers with set_bit off go to num2 group.

traverse

Partition second number 2 by set_bit and XOR

Check if 2 & set_bit (2) is nonzero. It is nonzero, so XOR 2 into num1.

💡 Numbers with set_bit on go to num1 group.

Line:

if num & set_bit:
    num1 ^= num  # num=2
else:
    num2 ^= num

💡 Partitioning separates unique numbers by differing bit.

traverse

Partition third number 1 by set_bit and XOR

Check if 1 & set_bit (2) is zero, so XOR 1 into num2.

💡 Duplicates go to same group and cancel out.

Line:

if num & set_bit:
    num1 ^= num
else:
    num2 ^= num  # num=1

💡 Duplicates cancel in their group.

traverse

Partition fourth number 3 by set_bit and XOR

Check if 3 & set_bit (2) is nonzero, so XOR 3 into num1.

💡 Group XOR accumulates unique number bits.

Line:

if num & set_bit:
    num1 ^= num  # num=3
else:
    num2 ^= num

💡 num1 accumulates XOR of group with set_bit on.

traverse

Partition fifth number 2 by set_bit and XOR

Check if 2 & set_bit (2) is nonzero, so XOR 2 into num1.

💡 Duplicates cancel out in their group.

Line:

if num & set_bit:
    num1 ^= num  # num=2
else:
    num2 ^= num

💡 Duplicates cancel in num1 group.

traverse

Partition sixth number 5 by set_bit and XOR

Check if 5 & set_bit (2) is zero, so XOR 5 into num2.

💡 Unique numbers remain after duplicates cancel.

Line:

if num & set_bit:
    num1 ^= num
else:
    num2 ^= num  # num=5

💡 num2 accumulates XOR of group with bit off.

reconstruct

Final unique numbers found

num1 and num2 now hold the two unique numbers 3 and 5 respectively.

💡 Partitioning and XORing groups isolates unique numbers.

Line:return [num1, num2]

💡 The algorithm successfully isolated the two unique numbers.

from typing import List

def singleNumber(nums: List[int]) -> List[int]:
    xor = 0  # STEP 1
    for num in nums:
        xor ^= num  # STEP 2-7: XOR all numbers
    set_bit = xor & (-xor)  # STEP 8: isolate rightmost set bit
    num1 = 0  # STEP 9
    num2 = 0  # STEP 9
    for num in nums:
        if num & set_bit:  # STEP 10-15: partition and XOR
            num1 ^= num
        else:
            num2 ^= num
    return [num1, num2]  # STEP 16

if __name__ == '__main__':
    print(singleNumber([1,2,1,3,2,5]))  # Output: [3,5]

📊

Single Number III (Two Singles) - Watch the Algorithm Execute, Step by Step

Watching each XOR and bitwise operation helps you understand how bit manipulation isolates unique elements without extra memory.

Step 1/16

·Active fill★Answer cell

Initialize xor

xor ^= 1

────

💡 XOR with 0 yields the number itself.

xor ^= 2

──────

💡 XOR sets bits where inputs differ.

xor ^= 1

──────

💡 XORing duplicates cancels bits.

xor ^= 3

────

💡 XOR accumulates unique bits.

xor ^= 2

──────

💡 XOR accumulates unique bits.

xor ^= 5

────────

💡 Final XOR isolates combined unique bits.

set_bit = xor & (-xor)

=-6

──────

💡 Rightmost set bit isolates a differing bit.

Initialize num1, num2

num & set_bit == 0

────

💡 Partition by set_bit groups numbers.

num & set_bit != 0

──────

💡 Partitioning groups numbers by set_bit.

num & set_bit == 0

────

💡 Duplicates cancel in XOR group.

num & set_bit != 0

──────

💡 Group XOR isolates unique number.

num & set_bit != 0

────────────────

💡 Duplicates cancel in XOR group.

num & set_bit == 0

──────

💡 Unique number isolated in group.

Return unique numbers

💡 Unique numbers isolated by partitioning.

Key Takeaways

✓ XORing all numbers isolates the XOR of the two unique numbers.

This insight is hard to see from code alone because XOR properties are non-intuitive without bit-level visualization.

✓ Isolating the rightmost set bit in the XOR result allows partitioning numbers into two groups that separate the unique numbers.

Understanding how a single set bit can differentiate two numbers is clearer when visualized.

✓ Partitioning and XORing each group separately cancels duplicates and reveals the unique numbers.

Seeing duplicates cancel in each group helps grasp why XOR works for this problem.

Practice

(1/5)

1. Consider the following code snippet implementing the trie-based maximum XOR finder. Given the input array [2, 8], what is the return value of findMaximumXOR([2, 8])?

easy

A. 2

B. 8

C. 10

D. 0

Solution

Step 1: Insert numbers 2 and 8 into trie
2 in binary: 000...0010, 8 in binary: 000...1000. Trie stores bits for both numbers.
Step 2: For each number, find max XOR partner
For 2, try to find bits opposite to 2's bits in trie. At bit 3 (8's highest set bit), toggled bit exists, so max_xor |= 8. At bit 1, toggled bit exists, max_xor |= 2. Total max_xor = 10.
Final Answer:
Option C -> Option C
Quick Check:
2 XOR 8 = 10, which is maximum XOR [OK]

Hint: XOR of 2 and 8 is 10, max XOR found [OK]

Common Mistakes:

Confusing max_xor with input number
Off-by-one bit indexing
Returning XOR with self

2. You need to determine if a given positive integer can be expressed as 4 raised to some integer power (i.e., n = 4^k for k ≥ 0). Which approach guarantees an optimal O(1) time solution without loops or recursion?

easy

A. Use logarithms to check if log base 4 of the number is an integer.

B. Iteratively divide the number by 4 until it becomes 1 or a non-divisible remainder is found.

C. Check if the number is a power of two and then verify if the set bit is in an even position using bitmasking.

D. Use dynamic programming to build up powers of four and compare with the number.

Solution

Step 1: Understand the problem requirement
The problem asks for a constant-time check to determine if a number is a power of four, which means no loops or recursion.
Step 2: Evaluate approaches for O(1) time
Using bitmasking to check if the number is a power of two and if the single set bit is in an even position is a known O(1) approach. Logarithm checks involve floating point operations and can have precision issues, so they are not guaranteed to be optimal or reliable in constant time. Iterative division and dynamic programming are not O(1).
Final Answer:
Option C -> Option C
Quick Check:
Bitmasking approach uses constant time bit operations [OK]

Hint: Bitmasking checks power of two and bit position in O(1)

Common Mistakes:

Confusing power of two check with power of four
Using loops despite O(1) requirement
Relying on floating point logarithm checks which can be imprecise

3. What is the time complexity of the XOR approach to find the missing number in an array of length n containing numbers from 0 to n with one missing?

medium

A. O(n log n) due to sorting inside XOR operations

B. O(1) since XOR is a constant time operation

C. O(n^2) because XOR operations are nested

D. O(n) because it iterates over the range and array once each

Solution

Step 1: Identify loops in the XOR approach
There are two separate loops: one over range 0 to n, and one over the array of length n.
Step 2: Calculate total time complexity
Each loop runs O(n) times, so total time is O(n) + O(n) = O(n).
Final Answer:
Option D -> Option D
Quick Check:
No nested loops or sorting, linear time confirmed [OK]

Hint: Two separate linear loops sum to O(n) time [OK]

Common Mistakes:

Confusing XOR operations as nested loops
Assuming sorting inside XOR
Ignoring linear iteration over range

4. What is the time complexity of the bit manipulation approach using n & (n - 1) to check if a number is a power of two, assuming n is a 32-bit integer?

medium

A. O(n), where n is the input number

B. O(n log n), due to repeated bit operations

C. O(1), constant time since integer size is fixed

D. O(log n), proportional to the number of bits in n

Solution

Step 1: Identify the operation cost
The operation n & (n - 1) runs in constant time on fixed-width integers, such as 32-bit integers.
Step 2: Consider input size in bits
Since the integer size is fixed (32 bits), the operation is O(1) constant time.
Final Answer:
Option C -> Option C
Quick Check:
Bitwise operations on fixed-width integers are constant time [OK]

Hint: Bit ops on fixed-width integers are O(1) [OK]

Common Mistakes:

Assuming O(log n) for fixed-width integers
Confusing numeric value with bit length

5. Suppose you want to generate all permutations of n elements but now elements can be reused any number of times (i.e., permutations with repetition). Which modification to the bitmask DP approach is correct?

hard

A. Use iterative DP over sequence length without bitmask since visited state is irrelevant

B. Keep bitmask DP but allow setting bits multiple times to reuse elements

C. Remove bitmask tracking and use simple recursion with repeated choices allowed

D. Use bitmask DP but reset dp states after each iteration to allow reuse

Solution

Step 1: Understand reuse means no visited tracking needed
Since elements can be reused, the visited bitmask is no longer meaningful.
Step 2: Use DP over sequence length only
Iterative DP over length with choices from all elements at each step correctly generates permutations with repetition.
Final Answer:
Option A -> Option A
Quick Check:
Bitmask DP is unnecessary when elements can be reused [OK]

Hint: Reuse means no visited bitmask needed; track length only [OK]

Common Mistakes:

Trying to reuse bitmask DP without modification
Allowing bits to be set multiple times breaks bitmask logic

Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard

Initialize xor to 0

XOR with first number 1

XOR with second number 2

XOR with third number 1

XOR with fourth number 3

XOR with fifth number 2

XOR with sixth number 5

Find rightmost set bit in xor

Initialize num1 and num2 to 0

Partition first number 1 by set_bit and XOR

Partition second number 2 by set_bit and XOR

Partition third number 1 by set_bit and XOR

Partition fourth number 3 by set_bit and XOR

Partition fifth number 2 by set_bit and XOR

Partition sixth number 5 by set_bit and XOR

Final unique numbers found

Key Takeaways

Practice

Solution

Step 1: Insert numbers 2 and 8 into trie

Step 2: For each number, find max XOR partner

Final Answer:

Quick Check:

Solution

Step 1: Understand the problem requirement

Step 2: Evaluate approaches for O(1) time

Final Answer:

Quick Check:

Solution

Step 1: Identify loops in the XOR approach

Step 2: Calculate total time complexity

Final Answer:

Quick Check:

Solution

Step 1: Identify the operation cost

Step 2: Consider input size in bits

Final Answer:

Quick Check:

Solution

Step 1: Understand reuse means no visited tracking needed

Step 2: Use DP over sequence length only

Final Answer:

Quick Check:

Ready to prove it?