Single Number (XOR Self-Cancellation)

🎯

Single Number (XOR Self-Cancellation)

easyBIT_MANIPULATIONAmazonFacebookGoogle

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.

💡 This problem introduces the power of bitwise XOR operation, which can cancel out pairs of identical numbers. Beginners often struggle because they try to use extra data structures or sorting instead of leveraging XOR's unique properties.

📋

Problem Statement

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.

💡

Example

Input"[2, 2, 1]"

Output1

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

Input"[4,1,2,1,2]"

Output4

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

• Array with only one element → return that element
• Array where the single number is the first element → correct identification
• Array where the single number is the last element → correct identification
• Array with negative numbers → still correctly identifies single number

⚠️

Common Mistakes

Using addition or subtraction instead of XOR to cancel duplicates

Incorrect result because addition doesn't cancel duplicates uniquely

✅ Use XOR operator which has the cancellation property

Not initializing the XOR accumulator to zero

Result is incorrect or unpredictable

✅ Always initialize accumulator to 0 before XORing

Using extra data structures like hash maps unnecessarily

Increased space complexity, not meeting problem constraints

✅ Use XOR approach to achieve constant space

Assuming input array is sorted or trying to rely on order

Fails on unsorted inputs or leads to incorrect assumptions

✅ Do not assume order; XOR approach works regardless of order

Using == instead of === in JavaScript causing type coercion bugs

Potential incorrect comparisons leading to wrong results

✅ Use strict equality === in JavaScript

🧠

Brute Force (Nested Loops Checking Each Element)

💡 This approach exists to build intuition by directly checking each element's frequency, helping beginners understand the problem's requirements before optimizing.

Intuition

Check each element and count how many times it appears by scanning the entire array. The one that appears once is 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, return that element as the single number.
3. If no element is found with count 1 (should not happen per problem constraints), return -1.

💡 This algorithm is straightforward but inefficient because it repeatedly scans the array, which is easy to understand but slow.

</>

Code

def singleNumber(nums):
    for i in range(len(nums)):
        count = 0
        for j in range(len(nums)):
            if nums[i] == nums[j]:
                count += 1
        if count == 1:
            return nums[i]

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

Line Notes

for i in range(len(nums))Outer loop picks each element to check its frequency

count = 0Initialize count for current element

for j in range(len(nums))Inner loop counts occurrences of nums[i]

if nums[i] == nums[j]Check if elements match to increment count

if count == 1If element appears once, return it immediately

public class Solution {
    public static int singleNumber(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            int count = 0;
            for (int j = 0; j < nums.length; j++) {
                if (nums[i] == nums[j]) {
                    count++;
                }
            }
            if (count == 1) {
                return nums[i];
            }
        }
        return -1; // Should never reach here
    }

    public static void main(String[] args) {
        System.out.println(singleNumber(new int[]{4,1,2,1,2})); // Output: 4
    }
}

Line Notes

for (int i = 0; i < nums.length; i++)Outer loop selects each element to check frequency

int count = 0;Initialize count for current element

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

if (nums[i] == nums[j])Check if elements match to increment count

if (count == 1)Return element if it appears exactly once

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

int singleNumber(vector<int>& nums) {
    for (int i = 0; i < nums.size(); i++) {
        int count = 0;
        for (int j = 0; j < nums.size(); j++) {
            if (nums[i] == nums[j]) {
                count++;
            }
        }
        if (count == 1) {
            return nums[i];
        }
    }
    return -1; // Should never reach here
}

int main() {
    vector<int> nums = {4,1,2,1,2};
    cout << singleNumber(nums) << endl; // Output: 4
    return 0;
}

Line Notes

for (int i = 0; i < nums.size(); i++)Outer loop iterates over each element

int count = 0;Initialize count for current element

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

if (nums[i] == nums[j])Increment count when elements match

if (count == 1)Return element if it appears once

function singleNumber(nums) {
    for (let i = 0; i < nums.length; i++) {
        let count = 0;
        for (let j = 0; j < nums.length; j++) {
            if (nums[i] === nums[j]) {
                count++;
            }
        }
        if (count === 1) {
            return nums[i];
        }
    }
    return -1; // Should never reach here
}

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

Line Notes

for (let i = 0; i < nums.length; i++)Outer loop selects each element to check frequency

let count = 0;Initialize count for current element

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

if (nums[i] === nums[j])Check equality to increment count

if (count === 1)Return element if it appears once

⏱

Complexity

TimeO(n^2)

SpaceO(1)

For each element, we scan the entire array to count occurrences, resulting in n * n = n^2 operations.

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

Interview Verdict: TLE / Use only to introduce problem

This approach is too slow for large inputs but helps understand the problem before optimizing.

🧠

Sorting + Linear Scan

💡 Sorting groups duplicates together, making it easier to find the single number by checking neighbors. This approach is a natural improvement over brute force.

Intuition

Sort the array so duplicates are adjacent, then scan once to find the element that doesn't have a duplicate next to it.

Algorithm

1. Sort the array in ascending order.
2. Iterate through the array in steps of two, comparing pairs of elements.
3. If a pair does not match, the first element of that pair is the single number.
4. If all pairs match, the single number is the last element.

💡 Sorting simplifies the problem by grouping duplicates, but sorting costs O(n log n) time.

</>

Code

def singleNumber(nums):
    nums.sort()
    i = 0
    while i < len(nums) - 1:
        if nums[i] != nums[i+1]:
            return nums[i]
        i += 2
    return nums[-1]

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

Line Notes

nums.sort()Sort array to group duplicates

i = 0Initialize index for linear scan

while i < len(nums) - 1Loop through array in pairs

if nums[i] != nums[i+1]Check if current pair elements differ

return nums[i]Return single number if pair mismatch found

return nums[-1]If no mismatch, last element is single number

import java.util.Arrays;
public class Solution {
    public static int singleNumber(int[] nums) {
        Arrays.sort(nums);
        int i = 0;
        while (i < nums.length - 1) {
            if (nums[i] != nums[i+1]) {
                return nums[i];
            }
            i += 2;
        }
        return nums[nums.length - 1];
    }

    public static void main(String[] args) {
        System.out.println(singleNumber(new int[]{4,1,2,1,2})); // Output: 4
    }
}

Line Notes

Arrays.sort(nums)Sort array to group duplicates

int i = 0;Initialize index for scanning pairs

while (i < nums.length - 1)Loop through array in pairs

if (nums[i] != nums[i+1])Check if pair elements differ

return nums[i];Return single number if mismatch found

return nums[nums.length - 1];Return last element if no mismatch

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

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

int main() {
    vector<int> nums = {4,1,2,1,2};
    cout << singleNumber(nums) << endl; // Output: 4
    return 0;
}

Line Notes

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

int i = 0;Initialize index for scanning pairs

while (i < (int)nums.size() - 1)Loop through array in pairs

if (nums[i] != nums[i+1])Check if pair elements differ

return nums[i];Return single number if mismatch found

return nums.back();Return last element if no mismatch

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

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

Line Notes

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

let i = 0;Initialize index for scanning pairs

while (i < nums.length - 1)Loop through array in pairs

if (nums[i] !== nums[i+1])Check if pair elements differ

return nums[i];Return single number if mismatch found

return nums[nums.length - 1];Return last element if no mismatch

⏱

Complexity

TimeO(n log n)

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

Sorting takes O(n log n) time, then a single pass O(n) to find the single number.

💡 For n=1000, sorting means about 10,000 operations, which is better than brute force but not optimal.

Interview Verdict: Accepted but not optimal

This approach is acceptable but interviewers expect linear time and constant space solutions.

🧠

Optimal XOR Approach

💡 This approach leverages the XOR operation's unique properties to find the single number in linear time and constant space, which is the ideal solution.

Intuition

XOR of a number with itself is 0, and XOR with 0 is the number itself. XORing all numbers cancels out duplicates, leaving the single number.

Algorithm

1. Initialize a variable result to 0.
2. Iterate through each number in the array.
3. XOR the result with the current number.
4. After processing all numbers, result holds the single number.

💡 This algorithm is elegant and efficient, using XOR's cancellation property to solve the problem in one pass.

</>

Code

def singleNumber(nums):
    result = 0
    for num in nums:
        result ^= num
    return result

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

Line Notes

result = 0Initialize XOR accumulator to zero

for num in numsIterate over each element

result ^= numXOR current number with accumulator to cancel duplicates

return resultReturn the single number after all cancellations

public class Solution {
    public static int singleNumber(int[] nums) {
        int result = 0;
        for (int num : nums) {
            result ^= num;
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(singleNumber(new int[]{4,1,2,1,2})); // Output: 4
    }
}

Line Notes

int result = 0;Initialize XOR accumulator to zero

for (int num : nums)Iterate over each element

result ^= num;XOR current number with accumulator to cancel duplicates

return result;Return the single number after all cancellations

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

int singleNumber(vector<int>& nums) {
    int result = 0;
    for (int num : nums) {
        result ^= num;
    }
    return result;
}

int main() {
    vector<int> nums = {4,1,2,1,2};
    cout << singleNumber(nums) << endl; // Output: 4
    return 0;
}

Line Notes

int result = 0;Initialize XOR accumulator to zero

for (int num : nums)Iterate over each element

result ^= num;XOR current number with accumulator to cancel duplicates

return result;Return the single number after all cancellations

function singleNumber(nums) {
    let result = 0;
    for (const num of nums) {
        result ^= num;
    }
    return result;
}

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

Line Notes

let result = 0;Initialize XOR accumulator to zero

for (const num of nums)Iterate over each element

result ^= num;XOR current number with accumulator to cancel duplicates

return result;Return the single number after all cancellations

⏱

Complexity

TimeO(n)

SpaceO(1)

Single pass through the array with constant extra space.

💡 For n=1000, this means about 1000 operations, which is very efficient.

Interview Verdict: Accepted and optimal

This is the best approach to implement in interviews for this problem.

📊

All Approaches - One-Glance Tradeoffs

💡 Use the XOR approach in 95% of interviews because it is optimal in time and space.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2)	O(1)	No	N/A	Mention only - never code
2. Sorting + Linear Scan	O(n log n)	O(1) or O(n)	No	N/A	Mention as improvement, but not optimal
3. Optimal XOR Approach	O(n)	O(1)	No	N/A	Code this approach

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice all approaches, and know what interviewers expect.

How to Present

Step 1: Clarify the problem and constraints.Step 2: Explain the brute force approach to show understanding.Step 3: Discuss sorting to improve time complexity.Step 4: Present the XOR approach as the optimal solution.Step 5: Code the XOR solution and test with examples.

Time Allocation

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

What the Interviewer Tests

Understanding of bitwise operations, ability to optimize from naive to optimal, and clean coding.

Common Follow-ups

• What if every element appears thrice except one? → Use bitwise counting per bit position.
• Can you solve it without extra space? → XOR approach uses constant space.

💡 These follow-ups test deeper bit manipulation knowledge and space optimization skills.

🔍

Pattern Recognition

When to Use

1) Array with pairs except one unique element, 2) Need linear time and constant space, 3) Problem hints at bitwise operations, 4) XOR or cancellation keywords appear.

Signature Phrases

'every element appears twice except for one''find the single number''linear runtime and constant space'

NOT This Pattern When

Problems requiring sum or frequency counts without XOR properties, or those needing sorting or hashing.

Similar Problems

Single Number II - similar but elements appear thrice except oneMissing Number - uses XOR to find missing elementFind the Duplicate Number - related to detecting duplicates

Practice

1. Consider the following code to find the missing number in an array containing numbers from 0 to n with one missing. What is the value of xor_all just before the return statement when the input is [3, 0, 1]?

easy

A. 2

B. 3

C. 0

D. 1

Solution

1. Step 1: Trace xor_all after first loop (XOR 0 to 3)

   0 ^ 0 = 0, 0 ^ 1 = 1, 1 ^ 2 = 3, 3 ^ 3 = 0

2. Step 2: XOR xor_all with each array element

   0 ^ 3 = 3, 3 ^ 0 = 3, 3 ^ 1 = 2

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Final xor_all is 2, the missing number [OK]

Hint: XOR all indices and elements cancels pairs leaving missing number [OK]

Common Mistakes:

• Off-by-one in range causing wrong xor_all
• XORing only array or only indices
• Misreading xor_all updates

2. What is the time complexity of the optimal bitwise AND range algorithm that repeatedly clears the rightmost set bit of the upper bound until it is less than or equal to the lower bound?

medium

A. O(n), where n = right - left

B. O(1), constant time regardless of input size

C. O(k), where k is the number of differing bits between left and right

D. O(log n), where n = right

Solution

1. Step 1: Understand the loop behavior

   Each iteration clears the rightmost set bit of right, reducing the number of set bits.

2. Step 2: Count iterations

   The loop runs at most as many times as there are set bits in the difference between right and left, i.e., the differing bits.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Time depends on differing bits, not full range size [OK]

Hint: Loop runs per differing set bit, not per number in range [OK]

Common Mistakes:

• Assuming linear in range size
• Confusing log n with bit count
• Ignoring bit-clearing effect

3. Identify the bug in the following trie-based maximum XOR code snippet:

medium

A. Line with 'node = node.children[bit]' does not check if 'bit' exists in children.

B. Line with 'if bit not in node.children:' should check for toggled_bit instead.

C. Line with 'max_xor |= (1 << i)' should be outside the if condition.

D. Line with 'node = self.root' should be inside the for loop.

Solution

1. Step 1: Analyze traversal in findMaxXor

   When toggled_bit is not found, code moves to node.children[bit] without checking if bit exists, risking KeyError.

2. Step 2: Identify missing null check

   Should use node.children.get(bit) or check existence before accessing to avoid runtime error.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing check causes crash on inputs missing bit child [OK]

Hint: Always check child existence before traversal [OK]

Common Mistakes:

• Assuming child always exists
• Confusing toggled_bit check
• Misplacing max_xor update

4. Suppose you want to check if a number is a power of two but the input can be negative or zero, and you want to handle 64-bit integers efficiently. Which modification to the bit manipulation approach is correct?

hard

A. Use the condition n > 0 and (n & (n - 1)) == 0 to handle all cases correctly.

B. Use n & (n + 1) == 0 to handle negative numbers as well.

C. Use floating point division to check if log2(n) is an integer for negative inputs.

D. Ignore negative inputs and only check positive numbers with n & (n - 1) == 0.

Solution

1. Step 1: Understand input constraints

   Negative and zero inputs are not powers of two, so must be excluded explicitly.

2. Step 2: Apply correct bit manipulation check

   Check n > 0 first, then use n & (n - 1) == 0 to verify exactly one set bit.

3. Step 3: Confirm correctness for 64-bit integers

   This approach works efficiently for 64-bit integers as well, since bitwise ops are constant time.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Explicit positive check avoids errors on zero/negative inputs [OK]

Hint: Always check n > 0 before bitwise power-of-two test [OK]

Common Mistakes:

• Using incorrect bitwise operations
• Ignoring negative inputs
• Using floating point logs causing precision errors

5. If the problem changes so that elements can be reused unlimited times in subsets (i.e., multisets), which modification to the backtracking approach correctly generates all such subsets?

hard

A. Use bitmask enumeration as before without any changes

B. Change recursive call to backtrack(i + 1, path) to prevent reuse of elements

C. Sort the array and skip duplicates during recursion to avoid repeated subsets

D. Change recursive call to backtrack(i, path) to allow reuse of the current element

Solution

1. Step 1: Understand reuse means elements can appear multiple times

   Allowing reuse means after including nums[i], we can include it again in subsequent recursive calls.

2. Step 2: Modify recursion to call backtrack(i, path) instead of backtrack(i + 1, path)

   This keeps the index at i, allowing repeated inclusion of nums[i].

3. Step 3: Confirm other options break correctness

   Advancing index (i + 1) prevents reuse; skipping duplicates is unrelated to reuse; bitmask enumeration assumes unique inclusion per element.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Recursing with same index enables unlimited reuse [OK]

Hint: Reuse requires recursive call with same index [OK]

Common Mistakes:

• Forgetting to keep index same to allow reuse
• Assuming bitmask works unchanged for reuse