268. Missing Number

EasyBit ManipulationArrayHash TableMathBinary SearchSorting

Problem Description

The task is to find a single missing number in an array that contains n unique numbers from the range [0, n]. This means the array is one number short of the full set, and your job is to identify which number from the range is not present in the array. For example, if the array nums is given as [3,0,1], the number 2 is not included in the array but it is in the range [0, 3], so the output should be 2.

Intuition

The provided solution uses a bitwise XOR operation to find the missing number. XOR is a logical operation that outputs true or 1 only when the number of true inputs is odd. For two bits, it outputs 1 if the bits are different, and 0 if they are the same. When you XOR the same number together, the result is 0. If you XOR a number with 0, you get the number back. We use this property to our advantage.

The solution uses an XOR operation between matching indices and values from the range [0, n] and the elements in the array nums. Since the array is guaranteed to have n unique numbers and we're doing XOR with n+1 numbers (since the range is [0, n]), the number that is missing will be the one that does not have a pair and thus will be left after all XOR operations are done.

The solution code first enumerates over nums starting with 1 instead of 0 since the range in the problem is [0, n] and you want to XOR each number with its index. The operation ^= is used to apply XOR in place. The reduce function from the functools module then applies the XOR operation cumulatively to the items of the iterable — which in this case is each XOR operation of the index and value — and thus cumulatively XORs all the indices and values, resulting in the missing number.

Learn more about Math, Binary Search and Sorting patterns.

Solution Approach

The solution for finding the missing number from the array nums involves a clever use of the XOR bitwise operation. As explained in the intuition section, the properties of XOR can be wielded to pinpoint the missing integer. The reduce function and the xor function from the functools module in Python are used to apply the XOR operation across an iterable, which is a generator expression in this case.

Here's a step-by-step breakdown of the implementation:

The enumerate function is used to generate pairs of index and value from the array nums. The index starts from 1 instead of 0 to align with our XOR operation approach which requires an extra element from the range [0, n].
The generator expression (i ^ v for i, v in enumerate(nums, 1)) computes the XOR of the index and value for each element in the nums array. The index i would normally start from 0, but since we want to include n in the XOR operations, we start it from 1.
The reduce function then takes two arguments: the first is the xor function, which specifies how the elements should be combined; and the second is the generator expression. What reduce does is, it applies the xor operation cumulatively to the elements of the iterable—sequentially applying the xor operation starting from the first pair to the last.
Since XOR is associative, the order of the application doesn't matter, and the reduce operation will effectively XOR all indices from 1 to n and all values in nums. The one number that isn't paired and XOR'd (the missing number) will remain.

The result of the reduce operation is the missing number from the array, which is returned by the missingNumber function. The beauty of this solution lies in its time complexity which is O(n) due to the single pass through the array, and space complexity which is O(1) since no extra space is used aside from the variables to perform the calculation.

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 us take a small example to illustrate the solution approach. Suppose we are given an array nums as [4, 2, 3, 0]. Notice that in this case n is 4 as there are 5 unique numbers in the range [0-4], but we only have 4 numbers in the array. We should identify the missing number which is in the range [0, 4] but not in the array. Following the steps of the solution approach:

Generate pairs of index (starting from 1) and value from the array nums: The pairs will look like this (index, value) - (1, 4), (2, 2), (3, 3), (4, 0).
Compute the XOR of the index and value for each element:
- The XOR of (1, 4) is 1 ^ 4 = 5
- The XOR of (2, 2) is 2 ^ 2 = 0
- The XOR of (3, 3) is 3 ^ 3 = 0
- The XOR of (4, 0) is 4 ^ 0 = 4
Apply the reduce function over our pairs using the xor operation:
- Start with the first pair resulting value, which is 5.
- Sequentially XOR this with the result of each of the subsequent pairs:
  - 5 ^ 0 = 5 (from second pair)
  - 5 ^ 0 = 5 (from third pair)
  - 5 ^ 4 = 1 (from fourth pair)
Finally, we are left with the value 1 which is the result of the cumulative XOR so far. To find the missing number, we need to also XOR 1 with n (5 in this case because we should include 0 through n):
- 1 ^ 5 = 4

Now 4 is NOT the missing number; rather, it is the result of XORing all the indices with their respective values including the number n. Remember that by using the XOR operation, duplicate elements (the ones that exist in the array) should negate each other, leaving only the missing element. However, since we started the index from 1, we have not accounted for the 0th index.

To fix this, we must one more time XOR our current result 4 with 0 (the missing 0th index due to starting enumeration at 1):

4 ^ 0 = 4

At this point, we need to realize that we have XOR'd the number 4 twice: Once for the 0th index that was missing in our enumeration, and once for the value from the array nums[0]. Each number from 1 to n has been XOR'd twice except for the missing number, so these pairs have all canceled out, leaving us with just the missing number.

Thus, the missing number from the array [4, 2, 3, 0] is 1, which is the missing element that did not get canceled out through the XOR operations. This is consistent with the range [0, 4] which contains 0, 1, 2, 3, 4 – every other number is present in the array except for 1.

Solution Implementation

1from functools import reduce  # Import reduce function from functools module.
2from operator import xor  # Import xor function from operator module.
3
4class Solution:
5    def missingNumber(self, nums):
6        """
7        Find the missing number in the array `nums` containing n distinct numbers in the 
8        range [0, n].
9
10        Args:
11        nums (List[int]): The input array with missing number.
12
13        Returns:
14        int: The missing number from the array.
15        """
16        # Apply the xor operator (^) between each number's index (i) and its value (v) starting with index 1.
17        # The reduce function then applies the xor operation cumulatively to the pairs of elements,
18        # which is needed since the input list misses one number, xor with the missing number results in the number itself.
19        # The xor of a number with itself is 0, so it will leave out normal pairs and single out the missing value.
20        # We enumerate starting with 1, since we want to include the number "n" in our comparisons.
21        return reduce(xor, (i ^ v for i, v in enumerate(nums, 1)))
22

1class Solution {
2  
3    // This method finds the missing number in an array containing numbers from 0 to n
4    public int missingNumber(int[] nums) {
5      
6        // Length of the array should be one number short of the full set
7        int n = nums.length;
8        // Initialize answer with the last number (which is n since array is 0-indexed)
9        int result = n;
10      
11        // Iterating through the array
12        for (int i = 0; i < n; ++i) {
13          
14            // Apply XOR operation between the current index and the element at that index, and XOR that with the current result
15            // Since a number XORed with itself is 0 and a number XORed with 0 is the number itself, this will eventually leave us with only the missing number
16            result ^= i ^ nums[i];
17        }
18      
19        // Return the result which is the missing number
20        return result;
21    }
22}
23

1#include <vector> // Include the vector header for using the vector class
2
3class Solution {
4public:
5    int missingNumber(std::vector<int>& nums) {
6        // Calculate the size of the vector.
7        int n = nums.size();
8        // Initialize 'missing' to the size of the vector, as the array is
9        // supposed to contain all numbers from 0 to n, so 'n' is the initial candidate.
10        int missing = n;
11      
12        // Loop through the array elements.
13        for (int i = 0; i < n; ++i) {
14            // XOR 'missing' with the current index 'i' and the element at that index 'nums[i]'.
15            // The idea behind this is that when a number and its index are XOR'ed
16            // in the range from 0 to n, the only number that will not be cancelled
17            // out is the missing number.
18            missing ^= (i ^ nums[i]);
19        }
20
21        // Return the missing number after processing the entire array.
22        return missing;
23    }
24};
25

1function missingNumber(nums: number[]): number {
2    // Calculate the length of the given array.
3    const arrayLength = nums.length;
4
5    // Initialize the result with the length of the array. This covers the edge case
6    // where the missing number is exactly equal to the length of the array.
7    let result = arrayLength;
8
9    // Iterate through the array.
10    for (let i = 0; i < arrayLength; ++i) {
11        // XOR the current index with the current array element and the current result.
12        // This will cancel out all numbers from 0 to n except the missing one.
13        result ^= i ^ nums[i];
14    }
15
16    // Return the missing number once all numbers have been XOR'ed.
17    return result;
18}
19

Time and Space Complexity

The given Python code uses the reduce function and a generator expression to find the missing number in a list of unique integers ranging from 0 to n. Here's how we analyze the computational complexity:

Time Complexity

The time complexity of the code is O(n), where n is the length of the array nums. This is because the generator expression (i ^ v for i, v in enumerate(nums, 1)) iterates through each element of the array exactly once. The xor operation inside the generator expression is a constant-time operation, taking O(1) time. The reduce function then iterates through these n xor operations to combine them, which also takes O(n) time. So, the total time taken is linear in relation to the array's length.

Space Complexity

The space complexity of the code is O(1), meaning it uses constant space regardless of the input size. The generator does not create an additional list in memory; it computes the xor values on-the-fly. The reduce function only needs space for the accumulator to hold the intermediate xor results, which is a single integer value. Thus the overall space used does not scale with the size of the input array.

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:

Question 1 out of 10

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10]

[100, 33, 30]

[10, 12, 20]

I don’t know