Leetcode 268. Missing Number
Priyanshu Kumar
Backend engineer specializing in Django, REST APIs, and scalable web applications.
The "Missing Number" problem is a classic algorithmic challenge where you're given an array of distinct numbers ranging from 0 to nn. The task is to find the one number missing from this range.
Problem Explanation
Given an array nums containing n distinct numbers from the range [0, n], you need to identify the missing number. Here's how it works:
Approach Using Sum Formula
Intuition:The sum of the first nn natural numbers is given by the formula n(n+1)22n(n+1). By calculating this sum and subtracting the sum of the numbers present in the array, we can find the missing number.Approach:
Complexity:
领英推荐
class Solution(object):
def missingNumber(self, nums):
sum_i = (len(nums) * (len(nums) + 1)) // 2
for num in nums:
sum_i -= num
return sum_i
Approach Using XOR Operator
Intuition:The XOR operation has a unique property where a number XORed with itself results in zero and a number XORed with zero results in the number itself. This property can be used to find the missing number.Approach:
Complexity:
class Solution(object):
def missingNumber(self, nums):
xor_all = len(nums)
for i in range(len(nums)):
xor_all ^= i ^ nums[i]
return xor_all
Conclusion
Both approaches efficiently solve the problem with linear time complexity and constant space usage. The sum formula approach leverages arithmetic properties, while the XOR approach uses bitwise operations for a clever solution.