Single Number III (Two Singles)

🎯

Single Number III (Two Singles)

mediumBIT_MANIPULATIONAmazonGoogleFacebook

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.

💡 This problem is about finding two unique numbers in an array where every other number appears twice. Beginners often struggle because the straightforward approach is not efficient and bit manipulation concepts like XOR and partitioning by set bits are not intuitive at first.

📋

Problem Statement

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

💡

Example

Input"[1,2,1,3,2,5]"

Output[3,5]

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.

• Array with minimum length 2 → output is the two elements themselves
• Two unique numbers are negative → output includes negative numbers
• All numbers are positive except the two unique → output includes positive numbers
• Unique numbers are the same magnitude but opposite signs → output includes both

⚠️

Common Mistakes

Using XOR without partitioning by set bit

Returns XOR of two unique numbers, not the numbers themselves

✅ Find a set bit in XOR and partition numbers accordingly

Using sorting but not handling edge cases at array ends

Misses unique elements at start or end

✅ Check boundary conditions carefully when scanning sorted array

Confusing negative numbers with bit operations

Incorrect set bit calculation or partitioning

✅ Use xor & (-xor) which works correctly with two's complement

Breaking early before finding both unique numbers

Returns incomplete or incorrect result

✅ Ensure loop continues until both unique numbers are found

🧠

Brute Force (Nested Loops)

💡 This approach exists to build intuition by trying all pairs and checking counts. It is simple but inefficient, helping beginners understand the problem constraints and why optimization is needed.

Intuition

Check each element and count how many times it appears by scanning the entire array. The two elements that appear once are the answer.

Algorithm

1. For each element in the array, count how many times it appears by scanning the entire array.
2. If the count is 1, add it to the result list.
3. Continue until two unique elements are found.
4. Return the two unique elements.

💡 This algorithm is straightforward but requires nested loops, which makes it slow for large inputs.

</>

Code

from typing import List

def singleNumber(nums: List[int]) -> List[int]:
    result = []
    n = len(nums)
    for i in range(n):
        count = 0
        for j in range(n):
            if nums[i] == nums[j]:
                count += 1
        if count == 1:
            result.append(nums[i])
            if len(result) == 2:
                break
    return result

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

Line Notes

result = []Initialize list to store unique elements

for i in range(n)Outer loop to pick each element

for j in range(n)Inner loop to count occurrences of nums[i]

if count == 1Check if current element is unique

import java.util.*;

public class SingleNumberIII {
    public static int[] singleNumber(int[] nums) {
        List<Integer> result = new ArrayList<>();
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            int count = 0;
            for (int j = 0; j < n; j++) {
                if (nums[i] == nums[j]) {
                    count++;
                }
            }
            if (count == 1) {
                result.add(nums[i]);
                if (result.size() == 2) {
                    break;
                }
            }
        }
        return new int[]{result.get(0), result.get(1)};
    }

    public static void main(String[] args) {
        int[] nums = {1,2,1,3,2,5};
        int[] res = singleNumber(nums);
        System.out.println(Arrays.toString(res)); // Output: [3, 5]
    }
}

Line Notes

List<Integer> result = new ArrayList<>()Store unique elements found

for (int i = 0; i < n; i++)Outer loop to select each element

for (int j = 0; j < n; j++)Inner loop to count occurrences of nums[i]

if (count == 1)Check if element is unique

#include <iostream>
#include <vector>
using namespace std;

vector<int> singleNumber(vector<int>& nums) {
    vector<int> result;
    int n = nums.size();
    for (int i = 0; i < n; i++) {
        int count = 0;
        for (int j = 0; j < n; j++) {
            if (nums[i] == nums[j]) {
                count++;
            }
        }
        if (count == 1) {
            result.push_back(nums[i]);
            if (result.size() == 2) {
                break;
            }
        }
    }
    return result;
}

int main() {
    vector<int> nums = {1,2,1,3,2,5};
    vector<int> res = singleNumber(nums);
    cout << "[" << res[0] << ", " << res[1] << "]" << endl; // Output: [3, 5]
    return 0;
}

Line Notes

vector<int> result;Container to hold unique numbers

for (int i = 0; i < n; i++)Outer loop to pick each element

for (int j = 0; j < n; j++)Inner loop counts occurrences of nums[i]

if (count == 1)Check if current element is unique

function singleNumber(nums) {
    const result = [];
    const n = nums.length;
    for (let i = 0; i < n; i++) {
        let count = 0;
        for (let j = 0; j < n; j++) {
            if (nums[i] === nums[j]) {
                count++;
            }
        }
        if (count === 1) {
            result.push(nums[i]);
            if (result.length === 2) {
                break;
            }
        }
    }
    return result;
}

// Test
console.log(singleNumber([1,2,1,3,2,5])); // Output: [3,5]

Line Notes

const result = []Initialize array to store unique elements

for (let i = 0; i < n; i++)Outer loop to select each element

for (let j = 0; j < n; j++)Inner loop counts occurrences of nums[i]

if (count === 1)Check if element is unique

⏱

Complexity

TimeO(n^2)

SpaceO(1)

For each element, we scan the entire array to count occurrences, resulting in O(n^2) time. Space is constant as we only store two unique elements.

💡 For n=1000, this means about 1,000,000 operations, which is too slow for large inputs.

Interview Verdict: TLE

This approach is too slow for large inputs and will time out, but it helps understand the problem and why optimization is needed.

🧠

Sorting and Linear Scan

💡 Sorting groups duplicates together, making it easier to find unique elements by checking neighbors. This approach is more efficient than brute force but still not optimal.

Intuition

Sort the array so duplicates are adjacent. Then scan once to find elements that don't have the same neighbor.

Algorithm

1. Sort the array.
2. Initialize an empty list for results.
3. Iterate through the array and compare each element with neighbors.
4. If an element is not equal to neighbors, add it to results.
5. Return the two unique elements.

💡 Sorting simplifies the problem by grouping duplicates, so a single pass can identify unique elements.

</>

Code

from typing import List

def singleNumber(nums: List[int]) -> List[int]:
    nums.sort()
    result = []
    n = len(nums)
    i = 0
    while i < n:
        if i == n - 1 or nums[i] != nums[i + 1]:
            result.append(nums[i])
            i += 1
        else:
            i += 2
        if len(result) == 2:
            break
    return result

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

Line Notes

nums.sort()Sort array to group duplicates

while i < nIterate through sorted array

if i == n - 1 or nums[i] != nums[i + 1]Check if current element is unique

if len(result) == 2Stop when two unique elements found

import java.util.*;

public class SingleNumberIII {
    public static int[] singleNumber(int[] nums) {
        Arrays.sort(nums);
        List<Integer> result = new ArrayList<>();
        int n = nums.length;
        int i = 0;
        while (i < n) {
            if (i == n - 1 || nums[i] != nums[i + 1]) {
                result.add(nums[i]);
                i++;
            } else {
                i += 2;
            }
            if (result.size() == 2) {
                break;
            }
        }
        return new int[]{result.get(0), result.get(1)};
    }

    public static void main(String[] args) {
        int[] nums = {1,2,1,3,2,5};
        int[] res = singleNumber(nums);
        System.out.println(Arrays.toString(res)); // Output: [3, 5]
    }
}

Line Notes

Arrays.sort(nums)Sort array to group duplicates

while (i < n)Iterate through sorted array

if (i == n - 1 || nums[i] != nums[i + 1])Check if current element is unique

if (result.size() == 2)Stop when two unique elements found

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> singleNumber(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    vector<int> result;
    int n = nums.size();
    int i = 0;
    while (i < n) {
        if (i == n - 1 || nums[i] != nums[i + 1]) {
            result.push_back(nums[i]);
            i++;
        } else {
            i += 2;
        }
        if (result.size() == 2) {
            break;
        }
    }
    return result;
}

int main() {
    vector<int> nums = {1,2,1,3,2,5};
    vector<int> res = singleNumber(nums);
    cout << "[" << res[0] << ", " << res[1] << "]" << endl; // Output: [3, 5]
    return 0;
}

Line Notes

sort(nums.begin(), nums.end())Sort array to group duplicates

while (i < n)Iterate through sorted array

if (i == n - 1 || nums[i] != nums[i + 1])Check if current element is unique

if (result.size() == 2)Stop when two unique elements found

function singleNumber(nums) {
    nums.sort((a, b) => a - b);
    const result = [];
    let i = 0;
    while (i < nums.length) {
        if (i === nums.length - 1 || nums[i] !== nums[i + 1]) {
            result.push(nums[i]);
            i++;
        } else {
            i += 2;
        }
        if (result.length === 2) {
            break;
        }
    }
    return result;
}

// Test
console.log(singleNumber([1,2,1,3,2,5])); // Output: [3,5]

Line Notes

nums.sort((a, b) => a - b)Sort array numerically to group duplicates

while (i < nums.length)Iterate through sorted array

if (i === nums.length - 1 || nums[i] !== nums[i + 1])Check if current element is unique

if (result.length === 2)Stop when two unique elements found

⏱

Complexity

TimeO(n log n)

SpaceO(1) or O(n) depending on sorting implementation

Sorting takes O(n log n) time. The linear scan is O(n). Overall time is dominated by sorting. Space depends on sorting algorithm used.

💡 For n=100000, sorting is feasible and much faster than brute force.

Interview Verdict: Accepted but not optimal

This approach passes but is not the best possible. It shows how sorting can simplify problems but bit manipulation can do better.

🧠

Optimal XOR and Partition by Set Bit

💡 This approach uses XOR properties to find the two unique numbers in linear time and constant space. It is the most efficient and elegant solution, but requires understanding XOR and bit manipulation.

Intuition

XOR all numbers to get xor of the two unique numbers. Find a set bit in xor to partition numbers into two groups, each containing one unique number. XOR each group to find the unique numbers.

Algorithm

1. XOR all numbers to get xor = num1 ^ num2, where num1 and num2 are unique.
2. Find any set bit in xor (rightmost set bit) to differentiate num1 and num2.
3. Partition numbers into two groups based on this set bit.
4. XOR numbers in each group separately to get num1 and num2.
5. Return the two unique numbers.

💡 This algorithm cleverly uses XOR to cancel duplicates and partitioning to separate unique numbers, achieving O(n) time and O(1) space.

</>

Code

from typing import List

def singleNumber(nums: List[int]) -> List[int]:
    xor = 0
    for num in nums:
        xor ^= num
    set_bit = xor & (-xor)  # rightmost set bit
    num1 = 0
    num2 = 0
    for num in nums:
        if num & set_bit:
            num1 ^= num
        else:
            num2 ^= num
    return [num1, num2]

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

Line Notes

xor = 0Initialize xor accumulator

for num in nums: xor ^= numXOR all numbers to get xor of two unique numbers

set_bit = xor & (-xor)Find rightmost set bit to partition numbers

if num & set_bitPartition numbers based on set bit

import java.util.*;

public class SingleNumberIII {
    public static int[] singleNumber(int[] nums) {
        int xor = 0;
        for (int num : nums) {
            xor ^= num;
        }
        int setBit = xor & (-xor); // rightmost set bit
        int num1 = 0, num2 = 0;
        for (int num : nums) {
            if ((num & setBit) != 0) {
                num1 ^= num;
            } else {
                num2 ^= num;
            }
        }
        return new int[]{num1, num2};
    }

    public static void main(String[] args) {
        int[] nums = {1,2,1,3,2,5};
        int[] res = singleNumber(nums);
        System.out.println(Arrays.toString(res)); // Output: [3, 5]
    }
}

Line Notes

int xor = 0Initialize xor accumulator

for (int num : nums) { xor ^= num; }XOR all numbers to get xor of unique numbers

int setBit = xor & (-xor)Find rightmost set bit to partition numbers

if ((num & setBit) != 0)Partition numbers based on set bit

#include <iostream>
#include <vector>
using namespace std;

vector<int> singleNumber(vector<int>& nums) {
    int xorVal = 0;
    for (int num : nums) {
        xorVal ^= num;
    }
    int setBit = xorVal & (-xorVal); // rightmost set bit
    int num1 = 0, num2 = 0;
    for (int num : nums) {
        if (num & setBit) {
            num1 ^= num;
        } else {
            num2 ^= num;
        }
    }
    return {num1, num2};
}

int main() {
    vector<int> nums = {1,2,1,3,2,5};
    vector<int> res = singleNumber(nums);
    cout << "[" << res[0] << ", " << res[1] << "]" << endl; // Output: [3, 5]
    return 0;
}

Line Notes

int xorVal = 0;Initialize xor accumulator

for (int num : nums) { xorVal ^= num; }XOR all numbers to get xor of unique numbers

int setBit = xorVal & (-xorVal);Find rightmost set bit to partition numbers

if (num & setBit)Partition numbers based on set bit

function singleNumber(nums) {
    let xor = 0;
    for (const num of nums) {
        xor ^= num;
    }
    const setBit = xor & (-xor); // rightmost set bit
    let num1 = 0, num2 = 0;
    for (const num of nums) {
        if ((num & setBit) !== 0) {
            num1 ^= num;
        } else {
            num2 ^= num;
        }
    }
    return [num1, num2];
}

// Test
console.log(singleNumber([1,2,1,3,2,5])); // Output: [3,5]

Line Notes

let xor = 0;Initialize xor accumulator

for (const num of nums) { xor ^= num; }XOR all numbers to get xor of unique numbers

const setBit = xor & (-xor);Find rightmost set bit to partition numbers

if ((num & setBit) !== 0)Partition numbers based on set bit

⏱

Complexity

TimeO(n)

SpaceO(1)

We do a constant number of passes over the array, each O(n). No extra space besides variables.

💡 For n=100000, this means about 3 passes over the array, which is very efficient.

Interview Verdict: Accepted and optimal

This is the best approach for this problem, combining efficiency and elegance using bit manipulation.

📊

All Approaches - One-Glance Tradeoffs

💡 In 95% of interviews, code the optimal XOR and partition approach because it is efficient and elegant.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2)	O(1)	No	Yes	Mention only - never code
2. Sorting and Linear Scan	O(n log n)	O(1) or O(n)	No	Yes	Good fallback if bit manipulation is unclear
3. Optimal XOR and Partition by Set Bit	O(n)	O(1)	No	Yes	Code this approach

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start with brute force to clarify the problem, then discuss better approaches, and finally implement the optimal solution.

How to Present

Step 1: Clarify the problem and constraints.Step 2: Explain the brute force approach and its inefficiency.Step 3: Suggest sorting to improve time complexity.Step 4: Introduce XOR properties and partitioning by set bit for optimal solution.Step 5: Code the optimal solution and test with examples.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

The interviewer tests your understanding of bit manipulation, ability to optimize from brute force, and coding accuracy.

Common Follow-ups

• What if there are more than two unique numbers? → Use generalized XOR or hash maps.
• Can you solve it without sorting or extra space? → Yes, using XOR and partitioning.

💡 These follow-ups test your ability to generalize and optimize further, common in interviews.

🔍

Pattern Recognition

When to Use

1) Array with exactly two unique elements, 2) All others appear twice, 3) Need O(n) time and O(1) space, 4) Bit manipulation is allowed

Signature Phrases

exactly two elements appear only onceall other elements appear exactly twice

NOT This Pattern When

Problems where multiple unique numbers appear more than twice or counting frequency problems

Similar Problems

Single Number - find one unique number using XORSingle Number II - find one unique number when others appear thrice

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 to generate Gray code sequence, what is the output of grayCode(2)?

easy

A. [1, 0, 3, 2]

B. [0, 1, 2, 3]

C. [0, 1, 3, 2]

D. [0, 2, 3, 1]

Solution

1. Step 1: Compute values for i in range(4)

   For i=0: 0 ^ (0>>1)=0; i=1: 1 ^ (0)=1; i=2: 2 ^ (1)=2^1=3; i=3: 3 ^ (1)=3^1=2

2. Step 2: Collect results in list

   The sequence is [0, 1, 3, 2], which matches the Gray code property.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Manual XOR calculation confirms the sequence [0,1,3,2] [OK]

Hint: XOR with right-shifted index generates Gray code directly [OK]

Common Mistakes:

• Confusing the order of XOR and shift
• Off-by-one errors in range leading to missing or extra elements
• Misinterpreting the output as binary numbers instead of integers

3. Identify the bug in the following code snippet for bitwise AND of numbers range:

medium

A. The bit-clearing operation 'right = right & (right - 1)' is incorrect.

B. There is no bug; the code works correctly.

C. The function should return 'left' instead of 'right'.

D. The loop condition should be 'right > left' instead of 'right != left'.

Solution

1. Step 1: Analyze loop condition

   The loop runs while right != left, which fails if right < left, causing infinite loop or incorrect behavior.

2. Step 2: Correct condition

   Changing condition to 'right > left' ensures loop terminates when right reaches or goes below left.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Loop condition must prevent infinite loops and handle equality correctly [OK]

Hint: Loop condition must be 'right > left' to terminate properly [OK]

Common Mistakes:

• Using '!=' instead of '>' causes infinite loops
• Misunderstanding bit-clearing operation
• Returning wrong variable

4. If the input number n can be negative or zero, and you want to check if its absolute value is a power of four, which modification to the optimal logarithm-based approach is correct?

hard

A. Remove the check for n <= 0 and directly compute log2(n)/2

B. Add a check to return False if n is zero or negative before applying logarithm on abs(n)

C. Use the brute force iterative division approach instead, as logarithm fails for negative inputs

D. Take the absolute value of n before the logarithm check and keep the rest unchanged

Solution

1. Step 1: Consider input domain

   Since n can be zero or negative, these are not powers of four, so must return False immediately.

2. Step 2: Apply logarithm check on absolute value

   After filtering invalid inputs, apply logarithm on abs(n) to check power of four.

3. Step 3: Finalize correct approach

   Adding a check to return False for zero or negative inputs before log check ensures correctness and avoids math domain errors.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Zero and negatives are filtered out before log check on abs(n) [OK]

Hint: Filter invalid inputs before log check on abs(n)

Common Mistakes:

• Removing input validation
• Applying log on negative numbers causing errors

5. Suppose you need to reverse bits of a 64-bit unsigned integer instead of 32-bit. Which modification to the optimal divide and conquer mask approach is correct?

hard

A. Extend masks to 64-bit constants and add an additional step shifting by 32 bits with proper masking.

B. Apply the 32-bit mask approach directly without changes; it works for any bit width.

C. Use the brute force bit-by-bit reversal loop since masks only work for 32 bits.

D. Use the same 32-bit masks and steps, but apply them twice to the lower and upper 32 bits separately.

Solution

1. Step 1: Understand mask size dependency

   The masks and shifts are designed for 32-bit integers and must be extended for 64-bit integers.

2. Step 2: Modify masks and add step

   Use 64-bit masks and add a final step shifting by 32 bits with masking to handle full 64-bit reversal.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   64-bit reversal requires 64-bit masks and an extra step [OK]

Hint: 64-bit reversal needs 64-bit masks and extra shift step [OK]

Common Mistakes:

• Trying to reuse 32-bit masks directly
• Splitting 64-bit into two 32-bit halves without merging
• Assuming brute force is only option for 64-bit