Missing Number

Array, Iterative Approach

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

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 in the range since it does not appear in nums.

Example 2:

Input: nums = [0,1]
Output: 2
Explanation: n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in the range since it does not appear in nums.

Example 3:

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 in the range since it does not appear in nums.

Constraints:

• n == nums.length

• 1 <= n <= 104

• 0 <= nums[i] <= n

• All the numbers of nums are unique.

Solutions

Approach - Brute Force Technique

This solution is considered a brute force approach because it checks each candidate number against all numbers in the array.

Steps

1. Outer Loop: The outer loop iterates over all numbers from 0 to nums.Length. Each number in this range is a potential candidate for the missing number.

2. Inner Loop and Flag Initialization: For each candidate number, a boolean flag found is initialized to false, and an inner loop iterates over all numbers in the array nums.

3. Number Checking: Inside the inner loop, it checks if the current number in the array nums is equal to the candidate number. If it is, it sets found to true and breaks the inner loop.

4. Missing Number Identification: After the inner loop, it checks the flag found. If found is still false, it means the candidate number was not found in the array nums, so it returns the candidate number as the missing number.

5. Completion: The function continues this process until it finds a missing number or it has checked all candidate numbers. If it has checked all candidate numbers and hasn’t found a missing number, it returns -1. However, according to the problem statement, there should always be one missing number, so this line should never be reached.

public class Solution {
    public int MissingNumber(int[] nums) {
        for (int i = 0; i <= nums.Length; i++) {
            bool found = false;
            for (int j = 0; j < nums.Length; j++) {
                if (nums[j] == i) {
                    found = true;
                    break;
                }
            }
            if (!found) {
                return i;
            }
        }
        return -1; // This line should never be reached.
    }
}

Complexity

• Time Complexity: O(N^2)

• Auxiliary Space: O(1)

Approach - Iterative Technique

Steps

1. Expected Sum Calculation: The function calculates the expected sum of all numbers from 0 to nums.Length using the formula for the sum of an arithmetic series: nums.Length*(nums.Length+1)/2. This sum is stored in expectedSum.

2. Actual Sum Calculation: The function then calculates the actual sum of all numbers in the array nums by iterating over each number in nums and adding it to actualSum.

3. Missing Number Calculation: Finally, the function calculates the missing number by subtracting actualSum from expectedSum. The result is the number that is missing from the array nums.

public class Solution {
    public int MissingNumber(int[] nums) {
        
        int expectedSum=nums.Length*(nums.Length+1)/2;
        int actualSum=0;
        foreach(var num in nums)actualSum+=num;
        return expectedSum-actualSum;
        
    }
}

Complexity

• Time Complexity: O(N)

• Auxiliary Space: O(1)