136. Single Number

EasyBit ManipulationArray

Problem Description

In this problem, you're given an array of integers nums where each element appears exactly twice, except for one element which appears only once. The task is to identify that single element that does not have a pair.

The conditions are:

The array is not empty (it contains at least one number).
The runtime complexity of your solution should be linear, in other words, O(n), which implies you can only traverse the array once.
You must use only constant extra space, so no additional arrays or data structures that grow with the size of the input.

Understanding the problem, the first thing that might come to mind is to count the occurrences of each number and return the one that has a count of one. However, this would require additional space proportional to the number of distinct elements, violating the space complexity requirement.

Therefore, we need a clever approach that uses a single variable to keep track of the unique element while traversing the array once. This is where bit manipulation comes in handy.

Intuition

The solution hinges on the concept of the XOR bitwise operation, which has two key properties that we can exploit:

Any number XORed with itself equals 0, i.e., a XOR a = 0.
Any number XORed with 0 equals the number itself, i.e., a XOR 0 = a.

Given these properties, we can iterate over all the numbers in the array and XOR them progressively. The key insight is that pairs of identical numbers will cancel each other out because of property 1 (resulting in 0), and single numbers will emerge unchanged because of property 2.

Imagine if we have an array like [2, 1, 4, 1, 2]. If we apply XOR to all elements sequentially, we'll end up with 2 XOR 1 XOR 4 XOR 1 XOR 2. The order of XOR operations doesn't matter due to its associative property, so we can group the identical numbers: (2 XOR 2) XOR (1 XOR 1) XOR 4. Now, using the first property, identical numbers XORed result in 0: 0 XOR 0 XOR 4. Finally, applying the second property, we are left with 4, which is the single number we're looking for.

This way, by taking the XOR of all numbers, we can isolate the unique element in a single pass and without using additional space, thus meeting all the problem's constraints. The reduce function with the xor operation from the Python's functools and operator modules, respectively, can be used to compactly write the solution as shown in the provided code.

Solution Approach

Referencing the Reference Solution Approach outlined earlier, the implementation uses a single Python function singleNumber that receives the list nums as its argument. To solve the problem, no explicit data structures are instantiated; instead, we leverage the reduce function and the xor from operator as the means to apply the XOR operation across all elements in the list.

The reduce function is a functional programming tool that applies a function of two arguments cumulatively to the items of a sequence, from left to right, so as to reduce the sequence to a single value. For our XOR operation, reduce is perfectly suited because it will take each element in nums in turn and apply the xor function, essentially folding the sequence down to one number through the cumulative XOR process.

Here's a step by step look at how reduce works in our context:

It initializes the "accumulator" (the running result of the XOR operations) with the first element of nums.
It then takes the next element and applies the xor function to this element and the accumulator.
The result of this operation becomes the new value of the accumulator.
This process repeats for each element in nums until all elements have been combined into one value by the XOR operation.

The xor function used here acts as our XOR logic, taking two numbers and returning their bitwise XOR result. In Python, the xor operation is represented by the caret symbol "^".

The final implementation looks like this:

from functools import reduce
from operator import xor

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        # Apply reduce to perform XOR on all elements of nums
        # This will leave us with the unique element
        return reduce(xor, nums)

By applying the XOR operation across all numbers using reduce, we're left with the unique number that doesn't have a duplicate in the list. Since the XOR of a number with itself is zero and the XOR of a number with zero is the number itself, all the paired numbers will cancel out, and only the unique one will remain. This aligns perfectly with the constraints of the problem, leading to a linear time complexity solution with constant space complexity.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's take a small example to illustrate the solution approach. Imagine we have an array nums = [5, 3, 5, 4, 3] and we want to find the single element that appears only once using the XOR operation.

We start with the first element (5) and initialize our accumulator with this value: accumulator = 5. Currently, our XOR chain looks like this: 5.
Move to the second element (3) and perform XOR with the accumulator: accumulator = 5 ^ 3. The XOR chain now looks like this: 5 ^ 3.
Next, go to the third element (another 5) and perform XOR: accumulator = (5 ^ 3) ^ 5. Since XOR of a number with itself is zero, it simplifies to: 3.
Proceed to the fourth element (4) and perform XOR: accumulator = 3 ^ 4. The XOR chain is now: 3 ^ 4.
Finally, take the last element (another 3) and perform XOR: accumulator = (3 ^ 4) ^ 3. This simplifies to 4, because XOR of a number with itself (3 in this case) cancels out.

At the end of this process, the accumulator holds the value 4, which is the number that appears only once in the array. Each step applies XOR to the current accumulator and the next element in the array, effectively canceling out pairs of numbers and leaving the unique number alone.

With the XOR properties in mind, it's clear that all matched pairs in the array will result in 0, and when 0 is XORed with the unique element, it will result in that unique element itself.

The Python implementation using reduce applies this process across the entire nums array, and we are directly left with the single number as the result, which is 4 in this case. This is the number that this solution approach will correctly identify as the single element.

Solution Implementation

1from functools import reduce  # Import reduce from functools module
2from operator import xor  # Import bitwise xor operator
3
4class Solution:
5    def singleNumber(self, nums):
6        # This method finds the element that appears only once in an array
7        # where every other element appears exactly twice.
8      
9        # It applies the reduce function to perform a cumulative xor operation 
10        # over all the numbers in the list. The xor of a number with itself is 0,
11        # and the xor of a number with 0 is the number itself. Thus, only the 
12        # element that appears once will remain after the reduction.
13      
14        return reduce(xor, nums)
15

1class Solution {
2    // Function to find the single number in an array where every element appears twice except for one
3    public int singleNumber(int[] nums) {
4        // Initialize the variable 'answer' with 0
5        int answer = 0;
6      
7        // Loop over each value in the array 'nums'
8        for (int value : nums) {
9            // Apply XOR operation between the 'answer' and the 'value'
10            // Since XOR of a number with itself is 0 and with 0 is the number itself,
11            // this will cancel out all pairs leaving the single number alone
12            answer ^= value;
13        }
14      
15        // Return the single number that doesn’t have a pair
16        return answer;
17    }
18}
19

1#include <vector> // Include the vector header for using the std::vector container.
2
3// Define the 'Solution' class.
4class Solution {
5public:
6    // Function to find the single number in a vector of integers.
7    // It utilizes bitwise XOR to find the unique element.
8    int singleNumber(std::vector<int>& nums) {
9        int singleNumber = 0; // Initialize the variable to store the result.
10
11        // Loop over each element in the vector.
12        for (int num : nums) {
13            singleNumber ^= num; // Apply XOR operation between the current result and the current number.
14        }
15
16        return singleNumber; // Return the result, which is the single number.
17    }
18};
19

1/**
2 * Finds the single number in an array of integers where each element appears twice except for one.
3 * @param {number[]} numbers - An array of numbers where all except one number are present twice.
4 * @returns {number} - The single number that appears only once in the array.
5 */
6function singleNumber(numbers: number[]): number {
7    // Use the reduce method to iterate through the array, applying the XOR (^) operator.
8    // The XOR operator will effectively cancel out duplicates, leaving the unique number.
9    // Starting value for the reduce function (second parameter) is 0.
10    return numbers.reduce((accumulator, currentValue) => accumulator ^ currentValue, 0);
11}
12
13// Usage example:
14// const numbersArray = [4, 1, 2, 1, 2];
15// const result = singleNumber(numbersArray);
16// console.log(result); // Outputs the single number, in this case 4
17

Time and Space Complexity

The time complexity of the code is O(n), where n is the length of the array nums. This is because the reduce function applies the xor operation sequentially to the elements of the list, which requires a single pass through all the elements.

The space complexity of the code is O(1). The space used does not depend on the size of the input list, as the xor operation is applied in-place and the reduce function only needs a constant amount of space to store the intermediate result of the xor operations.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12

1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18

1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

1 2 3 6 x x

1 2 3 x x x 6 x x

1 2 6 x x x 3 x x

I don't know