Practice
1. Given the following code and input, what is the final returned list?
easy
Solution
Step 1: Compute xor of all elements
xor = 2 ^ 4 ^ 2 ^ 5 = (2 ^ 2) ^ 4 ^ 5 = 0 ^ 4 ^ 5 = 1 (binary 0001)Step 2: Find rightmost set bit and partition
set_bit = xor & (-xor) = 1 & (-1) = 1. Partition nums by bit 1: group1 (bit set): 5, group2 (bit not set): 2,4,2. XOR group1 = 5, XOR group2 = 4.Final Answer:
Option C -> Option CQuick Check:
Output matches unique elements [OK]
Hint: Rightmost set bit partitions unique numbers correctly [OK]
Common Mistakes:
- Mixing order of output
- Incorrect xor calculation
- Miscomputing set bit
2. You are given an array where every element appears exactly twice except for one element that appears only once. Which approach guarantees finding the unique element in linear time and constant space?
easy
Solution
Step 1: Understand problem constraints
Every element except one appears twice, so duplicates cancel out under XOR.Step 2: Identify approach that leverages XOR properties
XOR of a number with itself is zero, and XOR with zero is the number itself, so XORing all elements leaves the unique one.Final Answer:
Option D -> Option DQuick Check:
XOR approach runs in O(n) time and O(1) space [OK]
Hint: XOR cancels duplicates perfectly [OK]
Common Mistakes:
- Sorting is O(n log n), not optimal
- Brute force is O(n²), inefficient
- DP is unrelated to this problem
3. The following code attempts to count set bits for all numbers from 0 to n using Brian Kernighan's trick. Identify the line containing the subtle bug that causes incorrect results.
def countBits(n):
res = []
for i in range(1, n + 1):
count = 0
x = i
while x:
x &= x - 1
count += 1
res.append(count)
return res
medium
Solution
Step 1: Check loop range correctness
The loop starts from 1, missing 0, so the count for 0 is never computed or appended.Step 2: Consequence of missing 0
Result array length is n instead of n+1, causing mismatch and incorrect output for input including 0.Final Answer:
Option A -> Option AQuick Check:
Including 0 is required to match problem specification [OK]
Hint: Loop must start at 0 to include zero count [OK]
Common Mistakes:
- Starting loop at 1 instead of 0
- Appending before counting
- Incorrect while condition
4. Identify the bug in the following code that attempts to count the number of 1 bits in a signed 32-bit integer:
def hammingWeight(n: int) -> int:
count = 0
while n != 0:
count += n & 1
n >>= 1
return count
medium
Solution
Step 1: Understand signed right shift behavior
In Python, right shifting a negative number propagates the sign bit, so n never becomes zero.Step 2: Analyze loop condition
Because n != 0 remains true for negative numbers, the loop never terminates, causing infinite loop.Final Answer:
Option A -> Option AQuick Check:
Signed right shift on negative numbers causes infinite loop [OK]
Hint: Signed right shift on negatives causes infinite loop [OK]
Common Mistakes:
- Confusing bitwise AND with logical AND
- Wrong shift direction
- Incorrect count initialization
5. Suppose the input array can contain duplicate numbers and missing numbers may appear multiple times (i.e., numbers can be reused). Which modification to the XOR partitioning approach correctly finds the two missing numbers?
hard
Solution
Step 1: Understand impact of duplicates
Duplicates break XOR approach because XOR assumes each number appears exactly once.Step 2: Choose correct approach
Frequency counting with a hash map correctly tracks counts and identifies missing numbers even with duplicates.Step 3: Why other options fail
Same XOR approach fails due to duplicates; modifying XOR by frequency is not feasible; sorting is O(n log n) and less efficient.Final Answer:
Option A -> Option AQuick Check:
Frequency counting handles duplicates correctly [OK]
Hint: XOR fails with duplicates; frequency map handles counts [OK]
Common Mistakes:
- Assuming XOR works with duplicates
- Trying to XOR multiple times per frequency
- Ignoring complexity of sorting