Single Number (XOR Self-Cancellation)

📋

Problem

Imagine you have a box of socks where every sock has a matching pair except one. You want to find the single unmatched sock quickly without sorting or extra space.

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one. You must implement a solution with linear runtime complexity and use only constant extra space.

1 ≤ nums.length ≤ 10^5-2^31 ≤ nums[i] ≤ 2^31 - 1Every element appears twice except for one element.

Edge cases: Array with only one element → return that elementArray where the single number is the first element → correct identificationArray where the single number is the last element → correct identification

</>

IDE

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

def singleNumber(nums):
    # Write your solution here
    pass

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

#include <vector>
using namespace std;

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

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

Common Bugs to Avoid

Wrong: 0Initializing XOR accumulator incorrectly or skipping XOR operation, resulting in default zero output.✅ Initialize accumulator to 0 and XOR all elements in a single loop: result = 0; for num in nums: result ^= num

Wrong: First element of arrayReturning first element without processing entire array or using greedy approach that fails to check all elements.✅ Do not return early; XOR all elements fully before returning the result.

Wrong: Incorrect number when input contains negative numbersIncorrect handling of signed integers or using data types that do not support negative values properly.✅ Use XOR directly on integers as is; no special handling needed for negatives.

Wrong: Timeout or no outputUsing nested loops or sorting approach causing O(n^2) or O(n log n) time complexity on large inputs.✅ Use XOR in a single pass to achieve O(n) time complexity.

✓

Test Cases

Focus on handling minimal and boundary inputs correctly.

Consider tricky inputs that expose common algorithmic mistakes.

Optimize your solution to run efficiently on large inputs.

t1_01basic

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

Expected1

⏱ Performance - must finish in 2000ms

2 appears twice and cancels out, leaving 1 as the single number.

💡 Consider how XOR operation cancels out pairs of identical numbers.

💡 Use the property that x ^ x = 0 and x ^ 0 = x to find the unique number.

💡 Iterate through nums XORing all elements; the result is the single number.

Why it failed: Failed to cancel duplicates correctly; likely missing XOR operation or incorrect loop. Fix by XORing all elements in a single pass.

✓ Correctly uses XOR to cancel duplicates and find the single number.

t1_02basic

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

Expected4

⏱ Performance - must finish in 2000ms

1 and 2 appear twice and cancel out, leaving 4 as the single number.

💡 XOR all elements to cancel duplicates regardless of order.

💡 Remember XOR is commutative and associative, so order doesn't matter.

💡 The final XOR result after processing all elements is the unique number.

Why it failed: Incorrect output due to not XORing all elements or resetting accumulator incorrectly. Fix by initializing accumulator to 0 and XOR all elements once.

✓ Successfully identifies the single number by XORing all elements.

t2_01edge

Input{"nums":[7]}

Expected7

⏱ Performance - must finish in 2000ms

Only one element, so it is the single number by definition.

💡 Check behavior when array length is 1.

💡 XOR of a single element with 0 is the element itself.

💡 Ensure no assumptions about array length greater than 1.

Why it failed: Fails single element input by not handling length 1 arrays or returning default value. Fix by returning the element if array length is 1 or XOR all elements regardless.

✓ Correctly returns the single element when array length is 1.

t2_02edge

Input{"nums":[0,1,1]}

Expected0

⏱ Performance - must finish in 2000ms

0 appears once, 1 appears twice and cancels out, leaving 0 as the single number.

💡 Test with zero as the single number.

💡 XOR with zero leaves the other number unchanged.

💡 Ensure XOR accumulator initializes to 0 and processes all elements.

Why it failed: Fails when single number is zero due to incorrect initialization or skipping zero. Fix by initializing XOR accumulator to 0 and XOR all elements.

✓ Correctly identifies zero as the single number.

t2_03edge

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

Expected-2

⏱ Performance - must finish in 2000ms

Negative numbers appear twice except -2 which is single; XOR handles signed integers correctly.

💡 Check behavior with negative numbers.

💡 XOR works on binary representation including sign bit.

💡 Ensure no assumptions about positive-only inputs.

Why it failed: Fails with negative numbers due to incorrect data type or sign handling. Fix by using XOR on all integers as is without sign assumptions.

✓ Correctly handles negative numbers and finds the single number.

t3_01corner

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

Expected3

⏱ Performance - must finish in 2000ms

3 is the single number; tests that duplicates are properly canceled even if single number is in the middle.

💡 Beware of greedy approaches that pick first non-duplicate without full scan.

💡 XOR all elements to avoid order-based mistakes.

💡 Do not stop early; process entire array to find unique number.

Why it failed: Greedy approach fails by returning first non-duplicate pair instead of XORing all. Fix by XORing all elements fully.

✓ Correctly finds single number in middle by full XOR.

t3_03corner

Input{"nums":[0,0,1]}

Expected1

⏱ Performance - must finish in 2000ms

Tests confusion between 0/1 values and unbounded duplicates; ensures XOR logic is applied correctly.

💡 Do not confuse 0 and 1 as boolean flags; treat as integers.

💡 XOR cancels pairs regardless of value.

💡 Initialize accumulator to 0 and XOR all elements.

Why it failed: Fails by treating 0 or 1 as special cases or boolean flags. Fix by applying XOR uniformly to all elements.

✓ Correctly identifies single number regardless of 0/1 values.

t4_01performance

Input{"nums":[100000,99999,100000,99998,99999,99997,99998,99996,99997,99996,99995,99994,99995,99993,99994,99992,99993,99991,99992,99991,99990,99989,99990,99988,99989,99987,99988,99986,99987,99986,99985,99984,99985,99983,99984,99982,99983,99981,99982,99981,99980,99979,99980,99978,99979,99977,99978,99976,99977,99976,99975,99974,99975,99973,99974,99972,99973,99971,99972,99971,99970,99969,99970,99968,99969,99967,99968,99966,99967,99966,99965,99964,99965,99963,99964,99962,99963,99961,99962,99961,99960,99959,99960,99958,99959,99957,99958,99956,99957,99956,99955,99954,99955,99953,99954,99952,99953,99951,99952,99951]}

Expectednull

⏱ Performance - must finish in 2000ms

n=100, O(n) XOR approach must complete within 2 seconds; brute force O(n^2) will time out.

💡 Use XOR to achieve linear time complexity.

💡 Avoid nested loops or sorting to prevent timeouts.

💡 Initialize accumulator to 0 and XOR all elements once.

Why it failed: TLE due to nested loops or sorting approach with O(n^2) or O(n log n) complexity on large inputs. Fix by using XOR in a single pass O(n).

✓ Solution runs in O(n) time using XOR, passing performance test.

Practice

1. Given the following code, what is the value of ones after processing the input [2, 2, 3, 2]?

easy

A. 3

B. 0

C. 2

D. 1

Solution

1. Step 1: Trace variable updates for each num

   After processing 2,2,3,2, the variable 'ones' ends up holding the unique number 3.

2. Step 2: Confirm final return value

   The function returns 'ones' which is 3, the single number appearing once.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Output matches expected unique element 3 [OK]

Hint: Final 'ones' holds the unique element after all iterations [OK]

Common Mistakes:

• Confusing 'ones' and 'twos' variables
• Off-by-one iteration errors

2. You need to compute the sum of two integers without using any arithmetic operators like + or -. Which of the following approaches guarantees a correct and efficient solution for all integer inputs, including negatives?

easy

A. Use bitwise XOR to add bits without carry and bitwise AND shifted left to compute carry, repeating until carry is zero.

B. Use dynamic programming to store partial sums and build up the final sum iteratively.

C. Use a greedy approach that adds bits from least significant to most significant, carrying over when needed.

D. Use brute force by incrementing one number by 1 repeatedly until the other number is added.

Solution

1. Step 1: Understand bitwise sum without +

   Bitwise XOR adds bits without carry, while bitwise AND identifies carry bits.

2. Step 2: Repeat until no carry remains

   Carry bits are shifted left and added recursively or iteratively until carry is zero, ensuring all bits are summed correctly.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Bitwise XOR and AND with carry loop is the classic sum without + [OK]

Hint: Sum without + uses XOR for sum and AND for carry [OK]

Common Mistakes:

• Thinking greedy bit-by-bit addition works without carry handling
• Using DP unnecessarily
• Brute force increment is inefficient

3. What is the time complexity of the XOR partitioning approach to find two missing numbers from 1 to n given an array of size n-2?

medium

A. O(n²) due to nested loops over the range and array

B. O(n) because it iterates over the range and array a constant number of times

C. O(n log n) due to bitwise operations on each element

D. O(1) since XOR operations are constant time

Solution

1. Step 1: Identify loops in the algorithm

   The algorithm iterates over the range 1 to n once and over the input array once, each in separate loops.

2. Step 2: Analyze operations inside loops

   Each iteration performs constant time XOR and bitwise operations, so total time is proportional to n.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Two linear passes -> O(n) time [OK]

Hint: Count loops and operations per iteration carefully [OK]

Common Mistakes:

• Assuming nested loops cause O(n²)
• Thinking bitwise ops add log n factor
• Confusing constant time with O(1) overall

4. Consider this buggy code snippet for finding two unique numbers. Which line contains the subtle bug?

medium

A. Line 8: set_bit calculation

B. Line 6: xor calculation loop

C. Line 3: xor initialization

D. Line 12: partitioning condition

Solution

1. Step 1: Identify how set_bit is computed

   Correct approach uses set_bit = xor & (-xor) to isolate rightmost set bit. Here, set_bit = xor misses this step.

2. Step 2: Understand impact of bug

   Without isolating rightmost set bit, partitioning fails, XOR groups won't separate unique numbers correctly.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Bug in set_bit calculation breaks partitioning [OK]

Hint: Isolate rightmost set bit with xor & (-xor) [OK]

Common Mistakes:

• Using xor directly as set_bit
• Breaking early before full XOR
• Misusing partition condition

5. What is the time complexity of the backtracking approach to generate all subsets of an input array of size n, assuming the array is sorted beforehand?

medium

A. O(n * 2^n)

B. O(n^2)

C. O(2^n)

D. O(n!)

Solution

1. Step 1: Identify number of subsets generated

   There are 2^n subsets in total.

2. Step 2: Calculate work done per subset

   Each subset can take up to O(n) time to copy or build, so total time is O(n * 2^n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Exponential subsets times linear work per subset [OK]

Hint: Each subset generation costs O(n), total subsets 2^n [OK]

Common Mistakes:

• Confusing O(2^n) as total time ignoring subset size
• Mistaking factorial or polynomial complexities