Single Number III (Two Singles)

📋

Problem

Imagine you have a list of IDs where every ID appears twice except for two unique IDs. You need to find those two unique IDs efficiently.

Given an integer array nums where exactly two elements appear only once and all the other elements appear exactly twice, find the two elements that appear only once. Return the two elements in any order.

1 ≤ nums.length ≤ 10^5-2^31 ≤ nums[i] ≤ 2^31 - 1Exactly two elements appear only once and all others appear twice

Edge cases: Array with minimum length 2 → output is the two elements themselvesTwo unique numbers are negative → output includes negative numbersAll numbers are positive except the two unique → output includes positive numbers

</>

IDE

def singleNumber(nums: list[int]) -> list[int]:public int[] singleNumber(int[] nums)vector<int> singleNumber(vector<int>& nums)function singleNumber(nums)

def singleNumber(nums: list[int]) -> list[int]:
    # Write your solution here
    pass

class Solution {
    public int[] singleNumber(int[] nums) {
        // Write your solution here
        return new int[2];
    }
}

#include <vector>
using namespace std;

vector<int> singleNumber(vector<int>& nums) {
    // Write your solution here
    return {};
}

function singleNumber(nums) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [3,4]Greedy approach returning first two unique numbers found instead of using XOR partitioning.✅ Implement XOR of all numbers, find a set bit, partition numbers by that bit, then XOR each group separately.

Wrong: [3,3]Counting occurrences instead of using XOR, leading to duplicate output or incorrect unique numbers.✅ Replace counting logic with XOR of all numbers and partitioning by set bit.

Wrong: [-4,5]Incorrect handling of negative numbers and sign bit in XOR partitioning.✅ Ensure XOR and partitioning handle signed 32-bit integers correctly, including sign bit.

Wrong: [1]Fails on minimum length input by returning only one unique number or empty output.✅ Handle input length 2 by returning both elements directly.

Wrong: TLE or timeoutUsing nested loops or sorting approach causing O(n^2) or O(n log n) time complexity.✅ Implement O(n) XOR partitioning algorithm to pass performance tests.

✓

Test Cases

Focus on handling edge cases like minimum input size and negative numbers correctly.

Avoid greedy or counting mistakes; rely on XOR partitioning technique.

Optimize your solution to linear time using XOR and bit partitioning.

t1_01basic

Input{"nums":[1,2,1,3,2,5]}

Expected[3,5]

⏱ Performance - must finish in 2000ms

XOR all numbers to get xor = 3 ^ 5. Find a set bit in xor to partition numbers into two groups and XOR separately to get 3 and 5.

💡 Use XOR to combine all numbers and find the XOR of the two unique numbers.

💡 Find a set bit in the XOR result to partition numbers into two groups.

💡 XOR each group separately to isolate the two unique numbers.

Why it failed: Output incorrect - likely missed partitioning by set bit or incorrect XOR logic. Fix by XORing all nums, find rightmost set bit, then XOR partitioned groups separately.

✓ Correctly implemented XOR partitioning and isolated the two unique numbers.

t1_02basic

Input{"nums":[4,1,2,1,2,5]}

Expected[4,5]

⏱ Performance - must finish in 2000ms

XOR all numbers to get xor = 4 ^ 5. Partition by a set bit and XOR groups to get 4 and 5.

💡 XOR all elements to get combined XOR of unique numbers.

💡 Identify a set bit in the XOR to split numbers into two groups.

💡 XOR each group to find the unique numbers.

Why it failed: Wrong output - probably did not partition numbers correctly by set bit or combined XOR incorrectly. Fix by using XOR of all nums and partitioning by a set bit.

✓ Correctly found unique numbers by XOR and partitioning.

t2_01edge

Input{"nums":[7,8]}

Expected[7,8]

⏱ Performance - must finish in 2000ms

Minimum length array with exactly two unique elements; output is the two elements themselves.

💡 Check behavior when input length is minimum (2).

💡 Ensure code handles no duplicates and returns both elements.

💡 Return input array as is when length is 2.

Why it failed: Fails on minimum length input - likely assumes duplicates exist. Fix by handling length 2 input as direct return.

✓ Handles minimum length input correctly.

t2_02edge

Input{"nums":[-1,-2,3,3,4,4]}

Expected[-2,-1]

⏱ Performance - must finish in 2000ms

Two unique numbers are negative; output includes negative numbers correctly.

💡 Verify handling of negative numbers in XOR operations.

💡 Remember XOR works with signed integers correctly.

💡 No special handling needed; just ensure bitwise ops handle negatives.

Why it failed: Incorrect output with negative numbers - likely sign bit mishandled. Fix by using signed 32-bit XOR operations properly.

✓ Correctly handles negative unique numbers.

t2_03edge

Input{"nums":[10,10,20,30]}

Expected[20,30]

⏱ Performance - must finish in 2000ms

All numbers are positive except the two unique; output includes positive unique numbers.

💡 Check that duplicates are properly ignored.

💡 Ensure XOR partitions correctly even if duplicates are at start.

💡 XOR all and partition by set bit to isolate unique positives.

Why it failed: Fails to isolate unique positives - likely incorrect grouping or XOR logic. Fix by proper partitioning by set bit.

✓ Correctly isolates positive unique numbers.

t3_01corner

Input{"nums":[2,2,3,3,4,5]}

Expected[4,5]

⏱ Performance - must finish in 2000ms

Test to catch greedy approach that picks first two unique numbers without XOR partitioning.

💡 Beware of greedy approaches that pick first two unique numbers found.

💡 Use XOR to find combined unique XOR, not just first unique elements.

💡 Partition by set bit and XOR groups to find correct unique numbers.

Why it failed: Greedy approach fails by returning first two unique elements found, ignoring XOR partitioning. Fix by implementing XOR partitioning method.

✓ Correctly avoids greedy trap and finds unique numbers via XOR.

t3_02corner

Input{"nums":[1,1,2,2,3,4]}

Expected[3,4]

⏱ Performance - must finish in 2000ms

Test to catch confusion between 0/1 knapsack and XOR logic - must not count occurrences but use XOR.

💡 Do not count occurrences; use XOR to find unique elements.

💡 XOR all numbers to get combined XOR of unique elements.

💡 Partition by set bit and XOR groups to isolate unique numbers.

Why it failed: Incorrectly counts occurrences instead of using XOR, leading to wrong output. Fix by replacing counting with XOR logic.

✓ Correctly uses XOR instead of counting occurrences.

t3_03corner

Input{"nums":[-3,1,1,-3,-4,-5]}

Expected[-5,-4]

⏱ Performance - must finish in 2000ms

Test to catch sign bit confusion and incorrect partitioning with negative numbers.

💡 Remember XOR works with signed integers including negatives.

💡 Partition by any set bit in XOR result, including sign bit.

💡 XOR each partition to find unique negative numbers.

Why it failed: Fails on negative numbers due to sign bit mishandling or partitioning error. Fix by correctly handling sign bit in partitioning.

✓ Correctly handles negative numbers and sign bit partitioning.

t4_01performance

Input{"nums":[1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13,14,14,15,15,16,16,17,17,18,18,19,19,20,20,21,21,22,22,23,23,24,24,25,25,26,26,27,27,28,28,29,29,30,30,31,31,32,32,33,33,34,34,35,35,36,36,37,37,38,38,39,39,40,40,41,41,42,42,43,43,44,44,45,45,46,46,47,47,48,48,49,49,50,50,51,51,52,52,53,53,54,54,55,55,56,56,57,57,58,58,59,59,60,60,61,61,62,62,63,63,64,64,65,65,66,66,67,67,68,68,69,69,70,70,71,71,72,72,73,73,74,74,75,75,76,76,77,77,78,78,79,79,80,80,81,81,82,82,83,83,84,84,85,85,86,86,87,87,88,88,89,89,90,90,91,91,92,92,93,93,94,94,95,95,96,96,97,97,98,98,99,99,100,100,101,102]}

Expectednull

⏱ Performance - must finish in 2000ms

Large input with n=102 to test O(n) XOR partitioning performance within 2 seconds.

💡 Optimal solution runs in O(n) time using XOR and partitioning.

💡 Avoid nested loops or sorting to prevent TLE.

💡 Use bitwise XOR and partition by set bit for linear time.

Why it failed: TLE due to nested loops or sorting approach (O(n^2) or O(n log n)). Fix by implementing O(n) XOR partitioning algorithm.

✓ Algorithm runs in O(n) time and passes performance test.

Practice

1. You need to generate all permutations of n distinct elements efficiently. Which approach best balances time and space by using a compact representation of visited elements and avoids redundant recomputation?

easy

A. Backtracking with a boolean visited array and recursion without memoization

B. Greedy algorithm that picks the next smallest unused element at each step

C. Bitmask DP with iterative tabulation that uses bitmasks to track visited elements and builds permutations bottom-up

D. Dynamic programming on subsets without bitmasking, using nested loops over all permutations

Solution

1. Step 1: Understand the problem constraints

   Generating all permutations requires enumerating all orderings of n elements, which is factorial in size. Efficient tracking of visited elements is crucial.

2. Step 2: Identify the approach that uses bitmasking

   Bitmask DP uses an integer to represent visited elements compactly, enabling memoization and iterative building of permutations without redundant recomputation.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Bitmask DP with iterative tabulation is the known optimal approach for this problem [OK]

Hint: Bitmask DP uses bits to track visited elements efficiently [OK]

Common Mistakes:

• Assuming greedy can generate all permutations correctly
• Using DP without bitmasking leads to inefficient state tracking

2. Given the following Python code that generates all subsets of nums = [1, 2, 3], what is the value of res after the function completes?

easy

A. [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

B. [[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]

C. [[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]

D. [[], [1], [1, 3], [1, 2], [1, 2, 3], [2], [2, 3], [3]]

Solution

1. Step 1: Trace backtrack calls and subsets added

   Initially, empty subset [] is added. Then 1 is added, subsets with 1 are generated, then 2, then 3, backtracking after each.

2. Step 2: Confirm order and completeness of subsets

   Subsets are generated in lexicographic order due to sorting and incremental indices: [], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3].

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Matches expected subsets order from backtracking [OK]

Hint: Backtracking adds subsets in sorted order [OK]

Common Mistakes:

• Confusing order of subsets or missing subsets

3. What is the time complexity of the Brian Kernighan's bit counting trick approach when counting set bits for all numbers from 0 to n?

medium

A. O(n * k) where k is the average number of set bits per number

B. O(n) because each number is processed in constant time

C. O(n * log n) because each number requires checking all bits

D. O(n^2) due to nested loops over bits and numbers

Solution

1. Step 1: Identify loops and operations

   Outer loop runs n+1 times; inner loop runs as many times as set bits in each number.

2. Step 2: Analyze average inner loop iterations

   Each iteration clears one set bit, so total inner loop iterations over all numbers is proportional to total set bits, roughly n * k.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Counting bits per number depends on number of set bits, not all bits [OK]

Hint: Time depends on total set bits, not total bits [OK]

Common Mistakes:

• Assuming O(n log n) because of bit length
• Thinking each number is constant time
• Confusing nested loops as quadratic

4. The following code attempts to generate all permutations of n elements using bitmask DP with iterative tabulation. Identify the line containing the subtle bug that causes dp[(1 << n) - 1] to remain empty.

def generate_permutations_iterative(n):
    dp = [[] for _ in range(1 << n)]
    # Missing initialization of dp[0]
    for mask in range(1 << n):
        for i in range(n):
            if not (mask & (1 << i)):
                for perm in dp[mask]:
                    dp[mask | (1 << i)].append(perm + [i])
    return dp[(1 << n) - 1]

medium

A. Line 2: dp initialization with empty lists

B. Line 7: Incorrect bitmask check condition

C. Line 5: Incorrect mask iteration range

D. Line 3: Missing dp[0] = [[]] initialization

Solution

1. Step 1: Check base case initialization

   dp[0] must be initialized to contain an empty permutation to start building others.

2. Step 2: Identify impact of missing dp[0] initialization

   Without dp[0] = [[]], dp[mask] lists remain empty, so no permutations are generated.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Adding dp[0] = [[]] fixes the empty result issue [OK]

Hint: dp[0] must be initialized to start building permutations [OK]

Common Mistakes:

• Forgetting to initialize dp[0]
• Misunderstanding bitmask iteration order

5. What is the time complexity of the recursive bitwise sum algorithm for adding two integers a and b without using the + operator, assuming 32-bit integers?

medium

A. O(1) constant time since integers are fixed size

B. O(log(max(a,b))) due to the number of bits processed

C. O(n), where n is the sum of a and b

D. O(n^2) because each recursion does bitwise operations on all bits

Solution

1. Step 1: Fixed integer size implies constant time

   Since integers are 32-bit fixed size, the number of operations is bounded by a constant.

2. Step 2: Recursion depth and bitwise operations are limited

   Maximum recursion depth and bitwise operations are limited by fixed bit width, so complexity is O(1).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Fixed 32-bit integers mean constant time complexity [OK]

Hint: Fixed integer size means constant time complexity [OK]

Common Mistakes:

• Confusing input magnitude with bit length
• Assuming complexity depends on numeric value
• Thinking recursion depth varies with input size