Bird
Raised Fist0
Interview Prepbit-manipulationmediumAmazonGoogleFacebook

Single Number III (Two Singles)

Choose your preparation mode4 modes available
🎯
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.
ApproachTimeSpaceStack RiskReconstructUse In Interview
1. Brute ForceO(n^2)O(1)NoYesMention only - never code
2. Sorting and Linear ScanO(n log n)O(1) or O(n)NoYesGood fallback if bit manipulation is unclear
3. Optimal XOR and Partition by Set BitO(n)O(1)NoYesCode 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/5)
1. Consider the following code snippet that finds the single number in an array using XOR. What is the value of result after processing the third element in the input [2, 3, 2]?
easy
A. 3
B. 1
C. 0
D. 2

Solution

  1. Step 1: Trace result after first element (2)

    result = 0 · 2 = 2
  2. Step 2: Trace result after second element (3)

    result = 2 · 3 = 1
  3. Step 3: Trace result after third element (2)

    result = 1 · 2 = 3
  4. Final Answer:

    Option A -> Option A
  5. Quick Check:

    Final XOR result is 3, the unique element [OK]
Hint: XOR accumulates unique element progressively [OK]
Common Mistakes:
  • Off-by-one in loop iteration
  • Confusing XOR with addition
  • Misreading variable updates
2. The following code attempts to find the missing number using XOR. Which line contains the subtle bug that causes incorrect results when the missing number is n?
medium
A. Line 3: initializing xor_all to 0
B. Line 7: returning xor_all without modification
C. Line 4: iterating only to n-1 instead of n
D. Line 6: XORing array elements

Solution

  1. Step 1: Analyze the loop range for XORing indices

    The loop runs from 0 to n-1 (range(n)), missing the number n itself.
  2. Step 2: Understand impact on missing number detection

    Since n is not XORed, if n is the missing number, it won't be accounted for, causing wrong output.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Changing loop to range(n+1) fixes the bug [OK]
Hint: Loop must include n to XOR all indices correctly [OK]
Common Mistakes:
  • Off-by-one in loop range
  • Forgetting to XOR n
  • Assuming initialization causes bug
3. Consider the following buggy Python code intended to generate Gray code sequence. Which line contains the subtle bug that breaks the Gray code property?
medium
A. Line 2: Using XOR with (i << 1) instead of (i >> 1)
B. Line 3: Incorrect range boundary in range(1 << n)
C. Line 1: Missing base case for n=0
D. Line 5: Printing the result instead of returning

Solution

  1. Step 1: Identify the bitwise operation used

    The code uses i ^ (i << 1) instead of the correct i ^ (i >> 1).
  2. Step 2: Understand impact on Gray code property

    Left shifting i doubles the value, causing incorrect bit patterns and breaking the one-bit difference property between consecutive numbers.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Correct Gray code uses right shift, not left shift [OK]
Hint: XOR with right shift generates Gray code; left shift breaks it [OK]
Common Mistakes:
  • Confusing left and right bit shifts in XOR formula
  • Ignoring base case n=0 which is trivial but not critical here
  • Misunderstanding range boundaries or print vs return
4. The following code attempts to find the maximum product of word lengths with no common letters. Which line contains a subtle bug that can cause incorrect results or inefficiency?
medium
A. Line 18: Checking bitmask overlap with bitwise AND
B. Line 10: Sorting masks by length in descending order
C. Line 14: Breaking outer loop when max product cannot improve
D. Line 6: Incorrect bit shift by adding 1 to character index

Solution

  1. Step 1: Identify bitmask construction

    Line 6 shifts bits by (ord(ch) - ord('a') + 1), which incorrectly shifts by 1 extra, causing wrong bitmask representation.
  2. Step 2: Impact of incorrect bitmask

    This causes overlap checks to fail or miss common letters, leading to incorrect max product or missed pruning opportunities.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Bitmask must shift by (ord(ch) - ord('a')) exactly [OK]
Hint: Bit shift must match character index exactly [OK]
Common Mistakes:
  • Off-by-one bit shifting in bitmask
  • Not pruning pairs after sorting
  • Incorrect overlap check logic
5. 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
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