Skip to main content
CodePeetCodePeet
CodePeet 250

Single Number

EASYProblemSolveExternal Links

Description

Given a non-empty array of integers nums, every element in the array appears exactly twice except for one element that appears only once. Your task is to find and return that single element.

The problem additionally requires that your solution runs in linear time complexity O(n) and uses only constant extra space O(1).

Examples

Example 1

Input: nums = [2, 2, 1]

Output: 1

Explanation: The number 1 appears only once in the array. The number 2 appears twice. Since 1 is the only element without a duplicate pair, we return 1.

Example 2

Input: nums = [4, 1, 2, 1, 2]

Output: 4

Explanation: The number 4 appears only once. The numbers 1 and 2 each appear twice. Regardless of the order elements are arranged in, 4 is the only unpaired element, so we return 4.

Example 3

Input: nums = [1]

Output: 1

Explanation: The array contains only one element. With no other elements present, that single element is automatically the answer.

Constraints

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

Editorial

Brute Force

Intuition

The simplest way to find which number appears only once is to check every number one by one. For each number in the array, we count how many times it appears by comparing it with every other element. If we find a number whose count is exactly 1, that is our answer.

Imagine you have a bag of colored marbles where every color has exactly two marbles, except one color which has only one marble. The brute force approach is to pick up each marble, then go through the entire bag counting how many marbles share that color. The first time you find a color with only one marble, you have found the odd one out.

Step-by-Step Explanation

Let's trace through with nums = [2, 2, 1]:

Step 1: Start the outer loop. Fix i=0, the element is nums[0]=2. We need to count how many times 2 appears in the entire array.

Step 2: Inner loop scans all elements:

  • j=0: nums[0]=2, matches! count becomes 1
  • j=1: nums[1]=2, matches! count becomes 2
  • j=2: nums[2]=1, does not match
    Final count for element 2 is 2.

Step 3: count=2 ≠ 1. Element 2 appears twice, so it is not the single number. Move to the next element.

Step 4: Fix i=1, element is nums[1]=2. Notice we are recounting the same value 2 — the brute force has no memory of previous work.

Step 5: Inner loop again finds count=2 for element 2. Not the single number. Move on.

Step 6: Fix i=2, element is nums[2]=1. Count how many times 1 appears.

Step 7: Inner loop:

  • j=0: nums[0]=2, no match
  • j=1: nums[1]=2, no match
  • j=2: nums[2]=1, match! count=1

Step 8: count=1 — Found the single number! Return 1.

Brute Force — Counting Frequency of Each Element — For each element, we scan the entire array counting how many times it appears. If the count is exactly 1, we have found our single number.

Algorithm

  1. For each element nums[i] in the array:
    • Initialize count = 0
    • For each element nums[j] in the array:
      • If nums[i] equals nums[j], increment count
    • If count equals 1, return nums[i]
  2. Return -1 (should never reach here given the problem constraints)

Code

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        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) {
                return nums[i];
            }
        }
        return -1;
    }
};
class Solution:
    def singleNumber(self, nums: list[int]) -> int:
        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:
                return nums[i]
        return -1
class Solution {
    public int singleNumber(int[] nums) {
        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) {
                return nums[i];
            }
        }
        return -1;
    }
}

Complexity Analysis

Time Complexity: O(n²)

The outer loop iterates through all n elements. For each element, the inner loop also iterates through all n elements to count its frequency. This gives us n × n = n² comparisons in the worst case.

Space Complexity: O(1)

We only use a single counter variable. No additional data structures are needed regardless of the input size.

Why This Approach Is Not Efficient

The brute force approach has O(n²) time complexity. With the constraint n ≤ 3 × 10⁴, this means up to approximately 9 × 10⁸ comparisons — far too slow for typical time limits of one second.

The core inefficiency is redundant counting. When we check the element at index 0 (value 2) and discover it appears twice, we already know that the element at index 1 (also value 2) will yield the same count. Yet the brute force blindly recounts it, performing the same n comparisons all over again.

Additionally, the problem explicitly requires O(n) linear runtime. We need a way to count each element's frequency just once. A hash map can store frequencies as we encounter elements, reducing the total work to a single pass through the array.

Better Approach - Hash Map

Intuition

Instead of recounting each element's frequency from scratch using nested loops, we can count all frequencies in a single pass using a hash map. We scan through the array once, recording each number and how many times we have seen it. After building this frequency map, we simply look for the number with a count of 1.

Think of it like a classroom attendance sheet. Instead of calling each student's name and having the entire class raise their hands to be counted (the brute force way), you walk through the room once and put a tally mark next to each student's name on the sheet. At the end, the student with only one tally mark is the one who does not have a partner.

Step-by-Step Explanation

Let's trace through with nums = [4, 1, 2, 1, 2]:

Step 1: Create an empty frequency map.

Step 2: Process nums[0]=4. Key 4 is not in the map → insert {4: 1}.
Map: {4: 1}

Step 3: Process nums[1]=1. Key 1 is not in the map → insert {1: 1}.
Map: {4: 1, 1: 1}

Step 4: Process nums[2]=2. Key 2 is not in the map → insert {2: 1}.
Map: {4: 1, 1: 1, 2: 1}

Step 5: Process nums[3]=1. Key 1 is already in the map with count 1 → increment to 2.
Map: {4: 1, 1: 2, 2: 1}

Step 6: Process nums[4]=2. Key 2 is already in the map with count 1 → increment to 2.
Map: {4: 1, 1: 2, 2: 2}

Step 7: Scan the map for any key with count exactly 1:

  • Key 4: count=1 → Found it!
  • Key 1: count=2, skip
  • Key 2: count=2, skip

Step 8: Return 4.

Hash Map — Building a Frequency Count in One Pass — We build a frequency map by scanning the array once. Each element is either inserted with count 1 or has its count incremented. The element with count 1 at the end is our answer.

Algorithm

  1. Create an empty hash map to store element → frequency mappings
  2. For each element num in the array:
    • Increment its count in the map: freq[num] += 1
  3. For each entry (key, count) in the map:
    • If count equals 1, return key
  4. Return -1 (should never reach here given problem constraints)

Code

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_map<int, int> freq;
        for (int num : nums) {
            freq[num]++;
        }
        for (auto& [key, count] : freq) {
            if (count == 1) {
                return key;
            }
        }
        return -1;
    }
};
class Solution:
    def singleNumber(self, nums: list[int]) -> int:
        freq = {}
        for num in nums:
            freq[num] = freq.get(num, 0) + 1
        for key, count in freq.items():
            if count == 1:
                return key
        return -1
class Solution {
    public int singleNumber(int[] nums) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int num : nums) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }
        for (Map.Entry<Integer, Integer> entry : freq.entrySet()) {
            if (entry.getValue() == 1) {
                return entry.getKey();
            }
        }
        return -1;
    }
}

Complexity Analysis

Time Complexity: O(n)

We scan the array once to build the frequency map — n insertions/increments each taking O(1) average time with a hash map. Then we scan the map entries (at most n/2 + 1 unique keys) to find the one with count 1. Total: O(n) + O(n) = O(n).

Space Complexity: O(n)

The hash map stores up to (n/2 + 1) unique elements, each with an integer count. In the worst case, this is proportional to n, so space usage is O(n).

Why This Approach Is Not Efficient

The hash map approach achieves O(n) time complexity, which satisfies the linear runtime requirement. However, it uses O(n) extra space to store the frequency map. The problem explicitly asks for a solution that uses only constant extra space — O(1).

Storing up to 15,001 unique key-value pairs (when n = 3 × 10⁴) is a significant memory overhead, especially when the problem guarantees a special structure: every number appears exactly twice except one.

This pairing property is a strong hint that a bitwise trick exists. The XOR (exclusive or) operation has the property that a ⊕ a = 0 — any number XORed with itself cancels to zero. If we XOR all elements together, paired numbers will cancel out, leaving only the single number. This achieves O(n) time with O(1) space.

Optimal Approach - XOR Bit Manipulation

Intuition

The XOR (exclusive or) bitwise operation has two key properties that solve this problem perfectly:

  1. Self-cancellation: Any number XORed with itself equals zero — a ⊕ a = 0
  2. Identity with zero: Any number XORed with zero equals itself — 0 ⊕ a = a
  3. Commutativity and Associativity: The order of XOR operations does not matter — a ⊕ b ⊕ c = c ⊕ a ⊕ b

If we XOR every number in the array together, every number that appears twice will cancel itself out (becoming 0), and only the number that appears once will survive.

For example: 4 ⊕ 1 ⊕ 2 ⊕ 1 ⊕ 2 = 4 ⊕ (1 ⊕ 1) ⊕ (2 ⊕ 2) = 4 ⊕ 0 ⊕ 0 = 4

Think of XOR like a light switch. Flipping a switch once turns the light on. Flipping the same switch again turns it off, returning to the original state. Each number that appears twice flips its switch on and then off, cancelling out. The single number flips its switch on and is never toggled off — it is the only light left on at the end.

Step-by-Step Explanation

Let's trace through with nums = [4, 1, 2, 1, 2] using XOR:

Step 1: Initialize result = 0 (binary: 000).

Step 2: XOR with nums[0]=4: result = 0 ⊕ 4 = 4.
Binary: 000 ⊕ 100 = 100.

Step 3: XOR with nums[1]=1: result = 4 ⊕ 1 = 5.
Binary: 100 ⊕ 001 = 101.

Step 4: XOR with nums[2]=2: result = 5 ⊕ 2 = 7.
Binary: 101 ⊕ 010 = 111.
No pairs have cancelled yet because we have not encountered any second occurrences.

Step 5: XOR with nums[3]=1: result = 7 ⊕ 1 = 6.
Binary: 111 ⊕ 001 = 110.
The two 1s have now cancelled out! The bits contributed by 1 (001) were toggled on at step 3 and toggled off here.

Step 6: XOR with nums[4]=2: result = 6 ⊕ 2 = 4.
Binary: 110 ⊕ 010 = 100.
The two 2s have also cancelled out! Only 4's bits remain.

Step 7: Final result = 4. This is the single number. Every paired element cancelled to zero, leaving only the unpaired element.

XOR Bit Manipulation — Pairs Cancel to Zero — XOR all elements together in a single pass. Duplicate pairs cancel out (a ⊕ a = 0), leaving only the single unpaired number (0 ⊕ a = a).

Algorithm

  1. Initialize result = 0
  2. For each element num in the array:
    • Compute result = result ⊕ num (XOR)
  3. Return result — this is the single number

Code

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int result = 0;
        for (int num : nums) {
            result ^= num;
        }
        return result;
    }
};
class Solution:
    def singleNumber(self, nums: list[int]) -> int:
        result = 0
        for num in nums:
            result ^= num
        return result
class Solution {
    public int singleNumber(int[] nums) {
        int result = 0;
        for (int num : nums) {
            result ^= num;
        }
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n)

We perform exactly n XOR operations in a single pass through the array. Each XOR operation takes O(1) time since it operates on fixed-size integers. Total time: n × O(1) = O(n).

Space Complexity: O(1)

We use only a single integer variable (result) to accumulate the XOR. No additional data structures are needed, regardless of input size. This meets the problem's explicit requirement of constant extra space.