136. Single Number - Explanation

Description

You are given a non-empty array of integers nums. Every integer appears twice except for one.

Return the integer that appears only once.

You must implement a solution with $O(n)$ runtime complexity and use only $O(1)$ extra space.

Example 1:

Input: nums = [3,2,3]

Output: 2

Example 2:

Input: nums = [7,6,6,7,8]

Output: 8

Constraints:

1 <= nums.length <= 10000
-10000 <= nums[i] <= 10000

Topics

Array Bit Manipulation

Recommended Time & Space Complexity

You should aim for a solution with O(n) time and O(1) space, where n is the size of the input array.

Hint 1

A brute force approach would iterate through the array, checking each element using a nested loop. If a duplicate is found, we continue to the next element; otherwise, the current element is the required number. This results in an O(n^2) solution. Can you think of a better way? Maybe a data structure can help detect duplicates efficiently.

Hint 2

We use a hash set, iterating through the array and adding elements that are not in the set while removing those that are already present. After the iteration, the required number remains in the hash set. This results in an O(n) space solution. Can you further optimize it? Maybe a bitwise operator could be useful here.

Hint 3

Think about the bitwise XOR ("^"). What is the result when two identical numbers are XORed?

Hint 4

When two identical numbers are XORed, they cancel out, resulting in zero. Since every number appears twice except for one, the XOR of the entire array gives the number that appears only once.

Company Tags

Google13 Amazon4 Microsoft2 Meta2 Bloomberg2 TCS11 Adobe8 Apple4 Cisco3 Yandex3 Goldman Sachs2 Airbnb2 Accenture2 Palantir Technologies2 Yahoo2

Prerequisites

Before attempting this problem, you should be comfortable with:

Bit Manipulation (XOR) - The optimal solution relies on XOR properties: a ^ a = 0 and a ^ 0 = a
Hash Set - Used in O(n) space solutions to track which numbers have been seen
Sorting - Alternative approach that groups duplicates together for easy identification

1. Brute Force

Intuition

We are given an array where every element appears twice except one, and we need to find that unique element.

The brute force idea is straightforward:

for each element in the array
check whether it appears anywhere else
if it does not match with any other element, then it must be the single number

This approach is simple and easy to understand, especially for beginners, because it directly follows the problem statement without using extra data structures or clever tricks.

Algorithm

Loop through each index i in the array:
Assume the current element nums[i] is unique (flag = true).
Loop through the array again with index j:
- If i != j and nums[i] == nums[j]:
  - the element is not unique
  - set flag = false and stop checking
After the inner loop:
- If flag is still true, return nums[i]
Since the problem guarantees exactly one unique element, the function will always return an answer.

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        for i in range(len(nums)):
            flag = True
            for j in range(len(nums)):
                if i != j and nums[i] == nums[j]:
                    flag = False
                    break
            if flag:
                return nums[i]

public class Solution {
    public int singleNumber(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            boolean flag = true;
            for (int j = 0; j < nums.length; j++) {
                if (i != j && nums[i] == nums[j]) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                return nums[i];
            }
        }
        return -1;
    }
}

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        for (int i = 0; i < nums.size(); i++) {
            bool flag = true;
            for (int j = 0; j < nums.size(); j++) {
                if (i != j && nums[i] == nums[j]) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                return nums[i];
            }
        }
        return -1;
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @return {number}
     */
    singleNumber(nums) {
        for (let i = 0; i < nums.length; i++) {
            let flag = true;
            for (let j = 0; j < nums.length; j++) {
                if (i !== j && nums[i] === nums[j]) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                return nums[i];
            }
        }
        return -1;
    }
}

public class Solution {
    public int SingleNumber(int[] nums) {
        for (int i = 0; i < nums.Length; i++) {
            bool flag = true;
            for (int j = 0; j < nums.Length; j++) {
                if (i != j && nums[i] == nums[j]) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                return nums[i];
            }
        }
        return -1;
    }
}

func singleNumber(nums []int) int {
    for i := 0; i < len(nums); i++ {
        flag := true
        for j := 0; j < len(nums); j++ {
            if i != j && nums[i] == nums[j] {
                flag = false
                break
            }
        }
        if flag {
            return nums[i]
        }
    }
    return 0
}

class Solution {
    fun singleNumber(nums: IntArray): Int {
        for (i in 0..nums.size - 1) {
            var flag = true
            for (j in 0..nums.size - 1) {
                if (i != j && nums[i] == nums[j]) {
                    flag = false
                    break
                }
            }
            if (flag) return nums[i]
        }
        return 0
    }
}

class Solution {
    func singleNumber(_ nums: [Int]) -> Int {
        for i in 0..<nums.count {
            var flag = true
            for j in 0..<nums.count {
                if i != j && nums[i] == nums[j] {
                    flag = false
                    break
                }
            }
            if flag {
                return nums[i]
            }
        }
        return -1
    }
}

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(1)$

2. Hash Set

Intuition

We are given an array where every number appears exactly twice except one, and we need to find that single number.

A convenient way to solve this is by using a hash set to track numbers as we iterate:

when we see a number for the first time, we add it to the set
when we see the same number again, we remove it from the set

Because:

duplicates are added once and removed once
only the number that appears exactly once will remain in the set

At the end, the set will contain only one element, which is the answer.

Algorithm

Initialize an empty set seen.
Traverse each number num in the array:
- If num is already in seen:
  - remove it from the set
- Otherwise:
  - add it to the set
After processing all numbers:
- the set contains exactly one element
Return the only element from the set.

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        seen = set()
        for num in nums:
            if num in seen:
                seen.remove(num)
            else:
                seen.add(num)
        return list(seen)[0]

public class Solution {
    public int singleNumber(int[] nums) {
        Set<Integer> seen = new HashSet<>();
        for (int num : nums) {
            if (seen.contains(num)) {
                seen.remove(num);
            } else {
                seen.add(num);
            }
        }
        return seen.iterator().next();
    }
}

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_set<int> seen;
        for (int num : nums) {
            if (seen.count(num)) {
                seen.erase(num);
            } else {
                seen.insert(num);
            }
        }
        return *seen.begin();
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @return {number}
     */
    singleNumber(nums) {
        const seen = new Set();
        for (const num of nums) {
            if (seen.has(num)) {
                seen.delete(num);
            } else {
                seen.add(num);
            }
        }
        return Array.from(seen)[0];
    }
}

public class Solution {
    public int SingleNumber(int[] nums) {
        var seen = new HashSet<int>();
        foreach (int num in nums) {
            if (seen.Contains(num)) {
                seen.Remove(num);
            } else {
                seen.Add(num);
            }
        }
        foreach (int num in seen) {
            return num;
        }
        return -1;
    }
}

func singleNumber(nums []int) int {
	seen := make(map[int]bool)
	for _, num := range nums {
		if seen[num] {
			delete(seen, num)
		} else {
			seen[num] = true
		}
	}
	for num := range seen {
		return num
	}
	return -1
}

class Solution {
    fun singleNumber(nums: IntArray): Int {
        val seen = HashSet<Int>()
        for (num in nums) {
            if (num in seen) {
                seen.remove(num)
            } else {
                seen.add(num)
            }
        }
        return seen.first()
    }
}

class Solution {
    func singleNumber(_ nums: [Int]) -> Int {
        var seen = Set<Int>()

        for num in nums {
            if seen.contains(num) {
                seen.remove(num)
            } else {
                seen.insert(num)
            }
        }

        return seen.first!
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

3. Sorting

Intuition

We are given an array where every element appears exactly twice except one, and we need to find that unique element.

Sorting helps simplify the problem:

after sorting, duplicate numbers appear next to each other
the single number will be the only element that does not have an identical neighbor

So we can scan the array in steps of two:

if nums[i] == nums[i + 1], they form a valid pair → skip both
if they are not equal, then nums[i] must be the unique element

This approach avoids extra space and relies on the structure created by sorting.

Algorithm

Sort the array nums.
Initialize an index i = 0.
While i < len(nums) - 1:
- If nums[i] == nums[i + 1]:
  - move to the next pair by setting i += 2
- Else:
  - return nums[i] (this is the single number)
If the loop ends, the unique element must be the last element:
- return nums[i]

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        nums.sort()
        i = 0
        while i < len(nums) - 1:
            if nums[i] == nums[i + 1]:
                i += 2
            else:
                return nums[i]
        return nums[i]

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

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

class Solution {
    /**
     * @param {number[]} nums
     * @return {number}
     */
    singleNumber(nums) {
        nums.sort((a, b) => a - b);
        let i = 0;
        while (i < nums.length - 1) {
            if (nums[i] === nums[i + 1]) {
                i += 2;
            } else {
                return nums[i];
            }
        }
        return nums[i];
    }
}

public class Solution {
    public int SingleNumber(int[] nums) {
        Array.Sort(nums);
        int i = 0;
        while (i < nums.Length - 1) {
            if (nums[i] == nums[i + 1]) {
                i += 2;
            } else {
                return nums[i];
            }
        }
        return nums[i];
    }
}

class Solution {
    fun singleNumber(nums: IntArray): Int {
        nums.sort()
        var i = 0
        while (i < nums.size - 1) {
            if (nums[i] == nums[i + 1]) {
                i += 2
            } else {
                return nums[i]
            }
        }
        return nums[i]
    }
}

class Solution {
    func singleNumber(_ nums: [Int]) -> Int {
        var nums = nums.sorted()
        var i = 0

        while i < nums.count - 1 {
            if nums[i] == nums[i + 1] {
                i += 2
            } else {
                return nums[i]
            }
        }

        return nums[i]
    }
}

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(1)$ or $O(n)$ depending on the sorting algorithm.

4. Bit Manipulation

Intuition

We are given an array where every number appears exactly twice except one, and we need to find that unique number.

This problem is a perfect fit for bit manipulation, specifically the XOR (^) operation.

Key properties of XOR:

a ^ a = 0 (a number XORed with itself cancels out)
a ^ 0 = a (XOR with 0 keeps the number unchanged)
XOR is commutative and associative, so order does not matter

Because of these properties:

all numbers that appear twice will cancel each other out
the number that appears once will remain

Algorithm

Initialize res = 0.
Iterate through each number in the array:
- update res = res ^ num
After processing all numbers:
- res contains the single number
Return res.

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        res = 0
        for num in nums:
            res = num ^ res
        return res

class Solution {
    /**
     * @param {number[]} nums
     * @return {number}
     */
    singleNumber(nums) {
        let res = 0;
        for (const num of nums) {
            res ^= num;
        }
        return res;
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

Common Pitfalls

Not Knowing XOR Properties

The optimal solution relies on understanding that a ^ a = 0 and a ^ 0 = a. Candidates unfamiliar with bitwise operations often resort to hash sets or sorting, missing the elegant $O(1)$ space solution. Memorizing these XOR properties is essential for bit manipulation problems.

Using Extra Space Unnecessarily

A common mistake is implementing a hash map or set to track occurrences when the problem explicitly asks for $O(1)$ extra space. While these approaches work functionally, they fail to meet the space constraint and miss the intended learning objective of the problem.