Find Missing Number Solution for Accenture
Company: Accenture · Difficulty: Easy · Topics: Array, Bit Manipulation, Math
Problem Statement
Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.
Key Understanding:
- The array should contain all numbers from 0 to n (inclusive)
- There is exactly one number missing
- All numbers in the array are unique
- The array is not necessarily sorted
Examples
Example 1:
Input: nums = [3,0,1]
Output: 2
Explanation:
- n = 3 since there are 3 numbers in the array
- The complete sequence should be [0,1,2,3]
- The array contains [0,1,3], so 2 is missing
- Visual representation: [0,1,2,3] → [0,1,_,3] where _ represents the missing 2
Example 2:
Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8
Explanation:
- n = 9 since there are 9 numbers in the array
- The complete sequence should be [0,1,2,3,4,5,6,7,8,9]
- The array contains [0,1,2,3,4,5,6,7,9], so 8 is missing
- Visual representation: [0,1,2,3,4,5,6,7,8,9] → [0,1,2,3,4,5,6,7,_,9]
Example 3:
Input: nums = [0]
Output: 1
Explanation:
- n = 1 since there is 1 number in the array
- The complete sequence should be [0,1]
- The array contains only [0], so 1 is missing
Intuition
The key insight is that we know the array should contain all numbers from 0 to n, so we can use mathematical properties to find the missing number efficiently.
Mathematical Properties:
1. Sum Formula: The sum of first n natural numbers is n*(n+1)/2
2. XOR Property: XORing a number with itself gives 0, and XORing with 0 gives the number itself
3. Range Property: All numbers from 0 to n should be present exactly once
Why These Approaches Work:
- Sum Approach: If we subtract the actual sum from the expected sum, we get the missing number
- XOR Approach: XORing all numbers from 0 to n with all numbers in the array cancels out all present numbers, leaving only the missing one
- Sorting Approach: After sorting, each position should contain its index value
Approach
Approach 1: Sum Formula (Optimal)
Algorithm:
1. Calculate the expected sum using the formula: n*(n+1)/2
2. Calculate the actual sum of all elements in the array
3. Return the difference: expected sum - actual sum
Why This Works:
- The expected sum includes the missing number
- The actual sum excludes the missing number
- Their difference gives us the missing number
Complexity Analysis:
- Time: O(n) - Single pass through the array
- Space: O(1) - Only constant variables needed
Approach 2: XOR Operation
Algorithm:
1. Initialize result = 0
2. XOR result with all numbers from 0 to n
3. XOR result with all numbers in the array
4. Return result
Why This Works:
- XOR has the property: a^a = 0 and a^0 = a
- All numbers from 0 to n XORed together = 0 (since each number appears once)
- All numbers in array XORed together = missing number (since each present number appears once)
- Final result = 0 ^ missing_number = missing_number
Complexity Analysis:
- Time: O(n) - Two passes through the array
- Space: O(1) - Only constant variables needed
Approach 3: Sorting and Linear Search
Algorithm:
1. Sort the array in ascending order
2. Iterate through the sorted array
3. Check if each position contains the expected value (index)
4. Return the first position where the value doesn't match the index
Why This Works:
- After sorting, the array should be [0,1,2,...,n] with one missing number
- The first position where array[i] ≠ i contains the missing number
Complexity Analysis:
- Time: O(n log n) - Due to sorting
- Space: O(1) if in-place sorting, O(n) if not
Dry Run
Let's trace through Example 1: nums = [3,0,1]
Sum Formula Approach:
Step 1: Calculate expected sum
- n = 3 (length of array)
- Expected sum = n*(n+1)/2 = 3*(3+1)/2 = 3*4/2 = 12/2 = 6
Step 2: Calculate actual sum
- Actual sum = 3 + 0 + 1 = 4
Step 3: Find missing number
- Missing number = Expected sum - Actual sum = 6 - 4 = 2
Verification: The array [3,0,1] is missing 2, which is correct.
XOR Approach:
Step 1: XOR all numbers from 0 to 3
- result = 0^1^2^3
- 0^1 = 1
- 1^2 = 3
- 3^3 = 0
- So result = 0
Step 2: XOR with all numbers in array
- result = 0^3^0^1
- 0^3 = 3
- 3^0 = 3
- 3^1 = 2
- Final result = 2
Verification: The missing number is 2, which matches our result.
Sorting Approach:
Step 1: Sort the array
- [3,0,1] → [0,1,3]
Step 2: Check each position
- Position 0: array[0] = 0, expected = 0 ✓
- Position 1: array[1] = 1, expected = 1 ✓
- Position 2: array[2] = 3, expected = 2 ✗
Result: Position 2 has value 3 instead of 2, so 2 is missing.
Key Insights
1. Mathematical Efficiency: The sum formula approach is both time and space optimal
2. XOR Elegance: XOR approach is mathematically elegant and handles overflow better than sum
3. Sorting Trade-off: Sorting approach is less efficient but more intuitive
4. Overflow Consideration: Sum approach might overflow for large arrays, XOR is safer
5. Single Pass: Both sum and XOR approaches can be done in a single pass
Edge Cases
1. Empty Array: Not possible as per constraints (1 ≤ nums.length ≤ 10^4)
2. Single Element: Array with one element, missing number is either 0 or 1
3. Large Numbers: Sum approach might overflow, XOR is safer
4. All Numbers Present: Not possible as per problem statement (exactly one number is missing)
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) - We traverse the array once
Space Complexity: O(1) - We use only constant extra space
Advantages:
- Simple and intuitive
- Single pass through array
- Constant space usage
Disadvantages:
- May overflow for large arrays
- Requires arithmetic operations
Solution 2: XOR Operation
Time Complexity: O(n) - We traverse the array once
Space Complexity: O(1) - We use only constant extra space
Advantages:
- No overflow issues
- Mathematically elegant
- Handles large numbers well
Disadvantages:
- Slightly less intuitive
- Requires understanding of XOR properties
Solution 3: Sorting and Linear Search
Time Complexity: O(n log n) due to sorting
Space Complexity: O(1) if in-place sorting, O(n) if not
Advantages:
- Very intuitive approach
- Easy to understand and implement
Disadvantages:
- Less efficient due to sorting
- Higher time complexity
- May use extra space depending on sorting algorithm