2. Missing Number

I have started learning Data Structures and Algorithms. Here is the second problem 268. Missing Number on LeetCode from a customised list of problems for my own learning.

Here is the code which I wrote first.

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        result = len(nums)
        for i in range(len(nums)-1):
            result = result^nums[i]
            result = i^result
        return

Issues in the Code

Incorrect Loop Range:

• The loop for i in range(len(nums)-1): skips the last element of the nums array. This is problematic because all numbers from 0 to n should be XORed to find the missing number.

Incorrect XOR Assignment:

• The line result = i^result should be result = result ^ i. This is because the XOR operation is commutative and associative, but the order of assignment matters for clarity and correctness.

No Return Statement:

• The function lacks a return statement at the end. It should return the final value of result.

Here is the correct code for the program

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        result = len(nums)  # Start with n (since one number is missing)
        for i in range(len(nums)):  # Loop through all indices
            result = result ^ nums[i]  # XOR with array elements
            result = result ^ i        # XOR with indices
        return result

Explanation of the Fixes

Loop Range:

• The loop should iterate over the entire range of indices in nums, i.e., range(len(nums)). This ensures all elements and indices are included in the XOR operation.

XOR Logic:

• The XOR operation (^) is used because:
• x ^ x = 0 (any number XORed with itself is 0).
• x ^ 0 = x (any number XORed with 0 remains unchanged).
• By XORing all numbers in the array and all indices from 0 to n, all matching numbers cancel out, leaving only the missing number.

Return Statement:

• The final value of result contains the missing number, so it must be returned.

Example Walk through

nums = [3, 0, 1]

Steps:

1. result = len(nums) = 3
2. Loop through nums and indices:

• i = 0: result = result ^ nums[0] ^ i = 3 ^ 3 ^ 0 = 0
• i = 1: result = result ^ nums[1] ^ i = 0 ^ 0 ^ 1 = 1
• i = 2: result = result ^ nums[2] ^ i = 1 ^ 1 ^ 2 = 2

Final result = 2 (the missing number).