Single Number

Find the single number that appears once in an array where every other number appears twice.

Language Selection

Choose your preferred programming language

Showing: Python

Single Number

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 a linear runtime complexity and use only constant extra space.

Examples

Example 1:

Input: nums = [2,2,1]
Output: 1
Explanation: Only 1 appears once, all others appear twice.

Example 2:

Input: nums = [4,1,2,1,2]
Output: 4
Explanation: Only 4 appears once, all others appear twice.

Example 3:

Input: nums = [1]
Output: 1
Explanation: Single element array.

Constraints

  • 1 <= nums.length <= 3 * 10^4
  • -3 * 10^4 <= nums[i] <= 3 * 10^4
  • Each element in the array appears twice except for one element which appears only once.

Approach 1: XOR Bit Manipulation (Optimal)

Algorithm

Use the XOR property: a ^ a = 0 and a ^ 0 = a. Since all numbers appear twice except one, XORing all numbers will cancel out the pairs and leave only the single number.

Steps:

  1. Initialize result to 0
  2. XOR all numbers in the array
  3. Return the result

Implementation

Python:

def singleNumber(nums):
    """
    Find single number using XOR
    Time: O(n)
    Space: O(1)
    """
    result = 0
    for num in nums:
        result ^= num
    return result

# One-liner version
def singleNumber_oneliner(nums):
    return reduce(lambda x, y: x ^ y, nums)

Java:

class Solution {
    /**
     * Find single number using XOR
     * Time: O(n)
     * Space: O(1)
     */
    public int singleNumber(int[] nums) {
        int result = 0;
        for (int num : nums) {
            result ^= num;
        }
        return result;
    }
}

Go:

func singleNumber(nums []int) int {
    /**
     * Find single number using XOR
     * Time: O(n)
     * Space: O(1)
     */
    result := 0
    for _, num := range nums {
        result ^= num
    }
    return result
}

JavaScript:

/**
 * Find single number using XOR
 * Time: O(n)
 * Space: O(1)
 */
function singleNumber(nums) {
    let result = 0;
    for (const num of nums) {
        result ^= num;
    }
    return result;
}

// One-liner version
const singleNumberOneLiner = nums => nums.reduce((acc, num) => acc ^ num, 0);

C#:

public class Solution {
    /// <summary>
    /// Find single number using XOR
    /// Time: O(n)
    /// Space: O(1)
    /// </summary>
    public int SingleNumber(int[] nums) {
        int result = 0;
        foreach (int num in nums) {
            result ^= num;
        }
        return result;
    }
}

Complexity Analysis

  • Time Complexity: O(n) - Single pass through array
  • Space Complexity: O(1) - Only using constant extra space

Approach 2: Hash Map (Alternative)

Algorithm

Use a hash map to count frequencies, then find the element with frequency 1.

Steps:

  1. Count frequency of each number
  2. Find the number with frequency 1
  3. Return that number

Implementation

Python:

from collections import Counter

def singleNumber_hashmap(nums):
    """
    Find single number using hash map
    Time: O(n)
    Space: O(n)
    """
    count = Counter(nums)
    for num, freq in count.items():
        if freq == 1:
            return num
    return -1  # Should never reach here

def singleNumber_hashmap_manual(nums):
    """
    Manual hash map implementation
    Time: O(n)
    Space: O(n)
    """
    freq = {}
    for num in nums:
        freq[num] = freq.get(num, 0) + 1
    
    for num, count in freq.items():
        if count == 1:
            return num
    return -1

Java:

import java.util.HashMap;
import java.util.Map;

class Solution {
    /**
     * Find single number using hash map
     * Time: O(n)
     * Space: O(n)
     */
    public int singleNumberHashMap(int[] nums) {
        Map<Integer, Integer> freq = new HashMap<>();
        
        // Count frequencies
        for (int num : nums) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }
        
        // Find single number
        for (Map.Entry<Integer, Integer> entry : freq.entrySet()) {
            if (entry.getValue() == 1) {
                return entry.getKey();
            }
        }
        
        return -1; // Should never reach here
    }
}

Go:

func singleNumberHashMap(nums []int) int {
    /**
     * Find single number using hash map
     * Time: O(n)
     * Space: O(n)
     */
    freq := make(map[int]int)
    
    // Count frequencies
    for _, num := range nums {
        freq[num]++
    }
    
    // Find single number
    for num, count := range freq {
        if count == 1 {
            return num
        }
    }
    
    return -1 // Should never reach here
}

JavaScript:

/**
 * Find single number using hash map
 * Time: O(n)
 * Space: O(n)
 */
function singleNumberHashMap(nums) {
    const freq = new Map();
    
    // Count frequencies
    for (const num of nums) {
        freq.set(num, (freq.get(num) || 0) + 1);
    }
    
    // Find single number
    for (const [num, count] of freq) {
        if (count === 1) {
            return num;
        }
    }
    
    return -1; // Should never reach here
}

C#:

using System.Collections.Generic;

public class Solution {
    /// <summary>
    /// Find single number using hash map
    /// Time: O(n)
    /// Space: O(n)
    /// </summary>
    public int SingleNumberHashMap(int[] nums) {
        var freq = new Dictionary<int, int>();
        
        // Count frequencies
        foreach (int num in nums) {
            freq[num] = freq.GetValueOrDefault(num, 0) + 1;
        }
        
        // Find single number
        foreach (var kvp in freq) {
            if (kvp.Value == 1) {
                return kvp.Key;
            }
        }
        
        return -1; // Should never reach here
    }
}

Complexity Analysis

  • Time Complexity: O(n) - Two passes through array
  • Space Complexity: O(n) - Hash map storage

Approach 3: Mathematical Approach

Algorithm

Use the mathematical property: 2 * sum(unique_elements) - sum(all_elements) = single_element

Steps:

  1. Calculate sum of all elements
  2. Calculate sum of unique elements (multiply by 2)
  3. Return the difference

Implementation

Python:

def singleNumber_math(nums):
    """
    Find single number using mathematical approach
    Time: O(n)
    Space: O(n) for set
    """
    unique_sum = sum(set(nums))
    total_sum = sum(nums)
    return 2 * unique_sum - total_sum

Java:

import java.util.HashSet;
import java.util.Set;

class Solution {
    /**
     * Find single number using mathematical approach
     * Time: O(n)
     * Space: O(n) for set
     */
    public int singleNumberMath(int[] nums) {
        Set<Integer> unique = new HashSet<>();
        int totalSum = 0;
        
        for (int num : nums) {
            unique.add(num);
            totalSum += num;
        }
        
        int uniqueSum = 0;
        for (int num : unique) {
            uniqueSum += num;
        }
        
        return 2 * uniqueSum - totalSum;
    }
}

Go:

func singleNumberMath(nums []int) int {
    /**
     * Find single number using mathematical approach
     * Time: O(n)
     * Space: O(n) for set
     */
    unique := make(map[int]bool)
    totalSum := 0
    
    for _, num := range nums {
        unique[num] = true
        totalSum += num
    }
    
    uniqueSum := 0
    for num := range unique {
        uniqueSum += num
    }
    
    return 2*uniqueSum - totalSum
}

JavaScript:

/**
 * Find single number using mathematical approach
 * Time: O(n)
 * Space: O(n) for set
 */
function singleNumberMath(nums) {
    const unique = new Set(nums);
    const totalSum = nums.reduce((sum, num) => sum + num, 0);
    const uniqueSum = [...unique].reduce((sum, num) => sum + num, 0);
    
    return 2 * uniqueSum - totalSum;
}

C#:

using System.Collections.Generic;
using System.Linq;

public class Solution {
    /// <summary>
    /// Find single number using mathematical approach
    /// Time: O(n)
    /// Space: O(n) for set
    /// </summary>
    public int SingleNumberMath(int[] nums) {
        var unique = new HashSet<int>(nums);
        int totalSum = nums.Sum();
        int uniqueSum = unique.Sum();
        
        return 2 * uniqueSum - totalSum;
    }
}

Complexity Analysis

  • Time Complexity: O(n) - Single pass through array
  • Space Complexity: O(n) - Set storage for unique elements

Key Insights

  1. XOR Properties: a ^ a = 0, a ^ 0 = a, a ^ b = b ^ a
  2. Pair Cancellation: XORing pairs cancels them out
  3. Space Optimization: XOR approach uses O(1) space
  4. Mathematical Insight: 2 * sum(unique) - sum(all) = single
  5. Hash Map Trade-off: More intuitive but uses O(n) space

Edge Cases

  1. Single Element: Array with one element
  2. Negative Numbers: XOR works with negative numbers
  3. Zero: XOR with zero returns the original number
  4. Large Numbers: XOR handles large integers correctly
  5. All Same: Not applicable (constraint ensures exactly one single)

Test Cases

def test_singleNumber():
    # Basic cases
    assert singleNumber([2, 2, 1]) == 1
    assert singleNumber([4, 1, 2, 1, 2]) == 4
    assert singleNumber([1]) == 1
    
    # Edge cases
    assert singleNumber([0, 0, 1]) == 1
    assert singleNumber([-1, -1, 2]) == 2
    assert singleNumber([1, 1, 0]) == 0
    
    # Larger arrays
    assert singleNumber([1, 2, 3, 4, 5, 1, 2, 3, 4]) == 5
    
    print("All tests passed!")

test_singleNumber()

Follow-up Questions

  1. Single Number II: What if every element appears three times except one?
  2. Single Number III: What if there are two single numbers?
  3. Missing Number: Find missing number in array [0, n]?
  4. Find Duplicate: Find duplicate number in array [1, n]?
  5. Two Missing Numbers: Find two missing numbers in array [1, n]?

Common Mistakes

  1. Wrong XOR Usage: Not understanding XOR properties
  2. Space Complexity: Using hash map when O(1) space is required
  3. Edge Cases: Not handling single element array
  4. Negative Numbers: Assuming XOR doesn’t work with negatives
  5. Return Type: Returning wrong data type

Interview Tips

  1. Start with XOR: Most efficient solution
  2. Explain XOR Properties: Show understanding of bit manipulation
  3. Discuss Trade-offs: Compare different approaches
  4. Handle Edge Cases: Mention single element and negative numbers
  5. Follow-up Ready: Be prepared for variations

Concept Explanations

XOR Bit Manipulation: XOR (exclusive OR) has unique properties that make it perfect for this problem. When you XOR a number with itself, you get 0. When you XOR with 0, you get the original number. This means that pairs of identical numbers will cancel out, leaving only the single number.

Why XOR Works: Since every number appears exactly twice except one, XORing all numbers will result in: (a ^ a) ^ (b ^ b) ^ ... ^ (single) = 0 ^ 0 ^ ... ^ single = single

Space Optimization: The XOR approach is optimal because it uses only O(1) extra space, meeting the problem’s constraint while providing O(n) time complexity.