Find Missing Number Solution for Wipro
Company: Wipro · Difficulty: Easy · Topics: Array, Mathematics
Problem Statement
Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.
The array is not necessarily sorted.
Examples
Example 1:
Input: nums = [3,0,1]
Output: 2
Explanation:
n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number since it does not appear in nums.
Example 2:
Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8
Explanation:
n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 8 is the missing number since it does not appear in nums.
Example 3:
Input: nums = [0]
Output: 1
Explanation:
n = 1 since there is 1 number, so all numbers are in the range [0,1]. 1 is the missing number since it does not appear in nums.
Example 4:
Input: nums = [1,2,3,4,5,6,7,8,9]
Output: 0
Explanation:
n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 0 is the missing number since it does not appear in nums.
Intuition
The key insight is that we can use the mathematical formula for the sum of first n natural numbers: sum = n*(n+1)/2. The missing number will be the difference between the expected sum and the actual sum of the array.
This works because:
- The array should contain numbers from 0 to n (inclusive)
- If one number is missing, the sum will be less than expected
- The difference between expected and actual sum gives us the missing number
Approach
Approach 1: Sum Formula (Optimal)
1. Calculate the expected sum of numbers from 0 to n using the formula: n*(n+1)/2
2. Calculate the actual sum of the given array
3. The missing number is the difference between expected and actual sum
Approach 2: Sorting and Linear Search
1. Sort the array
2. Check each position i, if nums[i] != i, then i is the missing number
3. If all positions match, then n is the missing number
Approach 3: XOR Operation
1. XOR all numbers from 0 to n with all numbers in the array
2. The result will be the missing number
Dry Run
Let's trace through Example 1: nums = [3,0,1], n = 3
Sum Formula Approach:
- Expected sum = 3*(3+1)/2 = 6
- Actual sum = 3 + 0 + 1 = 4
- Missing number = 6 - 4 = 2
Sorting Approach:
- After sorting: [0,1,3]
- Check position 0: nums[0] = 0 ✓
- Check position 1: nums[1] = 1 ✓
- Check position 2: nums[2] = 3 ≠ 2, so 2 is missing
XOR Approach:
- XOR all numbers 0 to 3: 0^1^2^3 = 0
- XOR with array elements: 0^3^0^1 = 2
- Result = 2
Key Insights
1. Mathematical Formula: The sum of first n natural numbers is n*(n+1)/2
2. Unique Property: Each number from 0 to n appears exactly once, except the missing one
3. Efficiency: Sum formula gives O(n) time and O(1) space
4. Edge Cases: Handle cases where 0 or n is missing
Edge Cases
1. Missing 0: Array contains [1,2,3,...,n]
2. Missing n: Array contains [0,1,2,...,n-1]
3. Single element: Array with one element
4. Empty array: Not possible as per constraints
Solution
⚠️ Disclaimer: Don't jump directly to the solution, try it out yourself first. Only look at the solution after you've given it a good attempt.
Solution 1: Sum Formula (Optimal)
Time Complexity: O(n) - Single pass through the array
Space Complexity: O(1) - Constant extra space
Solution 2: Sorting and Linear Search
Time Complexity: O(n log n) - Due to sorting
Space Complexity: O(1) - In-place sorting
Solution 3: XOR Operation
Time Complexity: O(n) - Single pass through the array
Space Complexity: O(1) - Constant extra space