LeetCode: Missing Number — Optimal Solution Explained

LeetCode: Missing Number — Optimal Solution Explained

Table of Content

• Introduction
• Intuition/Solution
• Step-by-Step Visual Guide
• Implementation Code

Introduction

In the world of programming problems and algorithm challenges, there are some problems that may seem simple at first glance but can offer multiple solutions, each with its own set of trade-offs. One such problem is the “Missing Number” problem. In this problem, you are given an array containing n distinct numbers taken from the range 0 to n, and your task is to find the one missing number in the range.

While there are various ways to approach this problem, today, we will explore a clever bitwise solution using the XOR operation.

We will guide you step by step, using clear visuals to demonstrate how the algorithm works, ensuring a thorough understanding of this powerful technique.

Intuition/Solution

In programming, XOR (exclusive OR) is a bitwise operation that compares two binary numbers bit by bit. For each pair of corresponding bits, the XOR operation outputs 1 if the bits are different, and 0 if the bits are the same. In other words, it returns true if only one of the input bits is true (1) and false (0) otherwise.

Input A | Input B | Output (A XOR B)
-------------------------------------
   0    |    0    |        0
   0    |    1    |        1
   1    |    0    |        1
   1    |    1    |        0

Here are two key properties of XOR that make it unique and useful in problem-solving:

1. A number XORed with itself results in 0 (A XOR A = 0).

Here’s an example…

101
XOR
101
-----
000

2. A number XORed with 0 results in the same number (A XOR 0 = A).

Here’s an example

111
XOR
000
-----
111

These properties allow XOR to be used as a tool to cancel out duplicates and isolate unique elements in a set of numbers, making it a powerful operation for solving various programming problems, including the Missing Number problem we’ve discussed.

With these properties in mind, we can find the missing number in the array by XORing all the numbers in the array and all the numbers from 0 to n. Since the array contains n distinct numbers in the range [0, n], the missing number will be the only number that doesn't have a duplicate in the XOR process.

Here’s a step-by-step explanation of the process:

1. Initialize a variable missing with the value 0.
2. Iterate through the array nums. For each element at index i, XOR the element with the value of missing and the number (i + 1). Update the value of missing with the result.
3. After the iteration, the value of missing will be the missing number in the range [0, n].

Step-by-Step Visual Guide

Case 1 :

Let’s take the same example with the array nums = [3, 0, 1]. The range of numbers is [0, 1, 2, 3]. The missing number is 2.

I will represent the numbers in their binary form, and we will perform the XOR operations in bits. Here’s the step-by-step explanation:

1. Initialize missing to 0 (binary: 00).
2. Iterate through the array:

1st Iteration

For i = 0, nums[i] = 3 (binary: 11). Perform the XOR operation with missing and (i + 1) = 1 (binary: 01).

missing = 00 ^ 11 ^ 01
        = 10 (binary, which is 2 in decimal)

Update missing to 2 (binary: 10).

2nd Iteration

For i = 1, nums[i] = 0 (binary: 00). Perform the XOR operation with missing and (i + 1) = 2 (binary: 10).

missing = 10 ^ 00 ^ 10
        = 00 (binary, which is 0 in decimal)

Update missing to 0 (binary: 00).

3rd Iteration

For i = 2, nums[i] = 1 (binary: 01). Perform the XOR operation with missing and (i + 1) = 3 (binary: 11).

missing = 00 ^ 01 ^ 11
        = 10 (binary, which is 2 in decimal)

Update missing to 2 (binary: 10).

Done

1. The value of missing is 2 (binary: 10), which is the missing number in the range [0, 1, 2, 3].

Implementation Code

Python

def missingNumber(nums):
    missing = 0
    for i, num in enumerate(nums):
        missing ^= num ^ (i + 1)
    return missing

Javascript

function missingNumber(nums) {
    let missing = 0;
    for (let i = 0; i < nums.length; i++) {
        missing ^= nums[i] ^ (i + 1);
    }
    return missing;
}