LeetCode 268: Missing Number Solution in Python – A Step-by-Step Guide

What Is LeetCode 268: Missing Number?

In LeetCode 268: Missing Number, you’re given an array nums with n distinct integers ranging from 0 to n, and your task is to find the one number missing from the complete set. For example, in [3,0,1], the numbers should be 0 to 3 (0, 1, 2, 3), so 2 is missing. This problem introduces clever ways to spot gaps, related to challenges like LeetCode 136: Single Number, but focuses on a complete range with one absentee.

Problem Statement

• Input: An integer array nums with n elements, containing distinct numbers from 0 to n.
• Output: An integer—the missing number in the range.
• Rules: Numbers are 0 to n; exactly one is missing; n is the array length.

Constraints

• n: 1 to 10^4.
• nums[i]: 0 to n (distinct).

Examples

• Input: nums = [3,0,1]
• Output: 2 (0 to 3: 0, 1, 2, 3; 2 is missing).
• Input: nums = [0,1]
• Output: 2 (0 to 2: 0, 1, 2; 2 is missing).
• Input: nums = [9,6,4,2,3,5,7,0,1]
• Output: 8 (0 to 9: 8 is missing).

Understanding the Problem: Finding the Missing Piece

To solve LeetCode 268: Missing Number in Python, we need to identify which number from 0 to n is absent in an array of n elements. The full set should be 0, 1, 2, ..., n, but with n numbers given, one is missing. For [3,0,1], n=3, the set should be [0,1,2,3], so 2 is the odd one out. A basic way—sorting and scanning for gaps—works but takes extra time. We’ll use two methods: 1. Best Solution (XOR Operation): O(n) time—fast and space-efficient. 2. Alternative Solution (Sum Difference): O(n) time—simple and intuitive.

Let’s dive into the best solution with a friendly, detailed walkthrough.

Best Solution: XOR Operation

Why This Is the Best Solution

The XOR operation approach is the top pick for LeetCode 268 because it runs in O(n) time—super quick—and uses O(1) space, needing just a single variable. It’s a clever trick that cancels out matching numbers, leaving the missing one behind, making it both efficient and a fun bit of math magic to learn.

How It Works

Picture this solution as a game of hide-and-seek with a twist: XOR (^ in Python) is like a spotlight that pairs up numbers and makes them disappear, leaving only the unpaired one—the missing number—shining through. Here’s how it works, step-by-step, explained simply:

• Step 1: XOR Basics:
• XOR is a binary operation: same numbers cancel (e.g., 3 ^ 3 = 0), different ones leave a result (e.g., 2 ^ 3 = 1).
• Property: XORing a number with itself is 0; XORing with 0 keeps it unchanged.
• Step 2: XOR the Indices and Numbers:
• Loop through the array, XORing each number with its index (0 to n-1).
• Also XOR with all numbers from 0 to n (the full set).
• Pairs in the array and full set cancel out, leaving the missing number.
• Step 3: Why It Works:
• Full set: 0, 1, 2, 3 (n=3).
• Array: 3, 0, 1 (missing 2).
• XOR indices (0, 1, 2) with array (3, 0, 1) and full set (0, 1, 2, 3):
• Every number present pairs up (e.g., 0 ^ 0, 1 ^ 1, 3 ^ 3), cancels to 0.
• Missing number (2) only appears once, stays in the result.
• Step 4: Simplify:
• XOR all array numbers, then XOR all indices 0 to n—result is the missing number.

It’s like a number dance—everyone pairs off except the one left standing!

Step-by-Step Example

Example: nums = [3,0,1]

• Step 1: n = 3, full set = [0, 1, 2, 3], array = [3, 0, 1].
• Step 2: XOR process:
• Start: result = 0.
• Array: 0 ^ 3 = 3, 3 ^ 0 = 3, 3 ^ 1 = 2.
• Indices: 2 ^ 0 = 2, 2 ^ 1 = 3, 3 ^ 2 = 1.
• Full set (0 to n): 1 ^ 0 = 1, 1 ^ 1 = 0, 0 ^ 2 = 2, 2 ^ 3 = 1.
• But simplify: XOR array (3 ^ 0 ^ 1) ^ (0 ^ 1 ^ 2 ^ 3) = 2.
• Step 3: Result = 2 (missing number).
• Result: 2.

Example: nums = [0,1]

• Step 1: n = 2, full set = [0, 1, 2].
• Step 2: XOR:
• Array: 0 ^ 1 = 1.
• Indices + n: 0 ^ 1 ^ 2 = 3 ^ 2 = 1.
• Total: 1 ^ 3 = 2.
• Result: 2.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained in a friendly way:

Copy codeclass Solution:
    def missingNumber(self, nums: List[int]) -> int:
        # Step 1: Start with 0
        result = 0

        # Step 2: XOR all array numbers
        for num in nums:
            result ^= num  # Combine with each number

        # Step 3: XOR all indices (0 to n)
        for i in range(len(nums) + 1):  # 0 to n inclusive
            result ^= i

        # Step 4: Result is the missing number
        return result

• Line 3: Start result at 0 (XOR identity).
• Line 5-6: XOR each number in nums into result.
• Line 8-9: XOR each index from 0 to n (array length + 1) into result.
• Line 11: After cancellations, result is the missing number.

• Time Complexity: O(n)—two passes through n elements.
• Space Complexity: O(1)—just one variable.

This solution is like a magic trick—XOR flips the numbers, and the missing one pops out!

Alternative Solution: Sum Difference Method

Why an Alternative Approach?

The sum difference method calculates the expected total of numbers from 0 to n and subtracts the actual sum of the array, revealing the missing number. It’s O(n) time too but feels more like basic math, making it a nice, clear way to see the problem before diving into bit tricks.

How It Works

Think of this as balancing a checkbook: you know what the total should be if everyone’s present, subtract what you’ve got, and the difference is who’s missing. Here’s how it works, step-by-step:

• Step 1: Calculate the expected sum of 0 to n using the formula n * (n + 1) // 2.
• Step 2: Calculate the actual sum of the array.
• Step 3: Subtract actual from expected—the result is the missing number.

It’s like counting chairs—total seats minus those filled equals the empty one!

Step-by-Step Example

Example: nums = [3,0,1]

• Step 1: n = 3, Expected = 3 * 4 // 2 = 6.
• Step 2: Actual = 3 + 0 + 1 = 4.
• Step 3: 6 - 4 = 2.
• Result: 2.

Example: nums = [0,1]

• Step 1: n = 2, Expected = 2 * 3 // 2 = 3.
• Step 2: Actual = 0 + 1 = 1.
• Step 3: 3 - 1 = 2.
• Result: 2.

Code for Sum Difference Approach

Copy codeclass Solution:
    def missingNumber(self, nums: List[int]) -> int:
        # Step 1: Get expected sum
        n = len(nums)
        expected = n * (n + 1) // 2

        # Step 2: Get actual sum
        actual = sum(nums)

        # Step 3: Difference is the missing number
        return expected - actual

• Time Complexity: O(n)—one pass for sum.
• Space Complexity: O(1)—just a few variables.

It’s a straight math path—simple and reliable.

Comparing the Two Solutions

• Best Solution (XOR):
• Pros: O(n) time, O(1) space, avoids overflow risk.
• Cons: XOR might feel tricky at first.
• Alternative Solution (Sum Difference):
• Pros: O(n) time, O(1) space, intuitive math.
• Cons: Sum could overflow for very large n (rare here).

XOR edges out for elegance and robustness.

Additional Examples and Edge Cases

Single Number

• [0] → 1 (n=1, 0 to 1)

Full Range Minus One

• [1,0,2] → 3

Large n

• [0,1,2,3] → 4

Both handle these smoothly.

Complexity Breakdown

• XOR:
• Time: O(n)—two linear passes.
• Space: O(1)—minimal.
• Sum Difference:
• Time: O(n)—one pass.
• Space: O(1)—minimal.

Both are fast, XOR slightly more robust.

Key Takeaways

• XOR: Cancels pairs, finds the odd one.
• Sum: Math finds the gap.
• Missing Number: Clever tricks beat brute force.
• Python Tip: Bit ops like ^ are handy—see [Python Basics](/python/basics).

Final Thoughts: Find Missing Numbers Like a Pro

LeetCode 268: Missing Number in Python is a delightful number hunt. The XOR solution dazzles with bit magic, while the sum method keeps it simple. Want more? Try LeetCode 136: Single Number or LeetCode 287: Find the Duplicate Number. Ready to search? Head to Solve LeetCode 268 on LeetCode and nab that missing number today!