Solution For Missing Number

The missing number problem on LeetCode asks us to find the missing number in an array of integers that is in the range of 0 to n. Here, n is the length of the array, and only one number is missing.

A simple approach to solve this problem is to use the mathematical formula for the sum of integers from 0 to n. The formula is

Sum = n * (n + 1) / 2

We know the expected sum of all the numbers in the array, which is using this formula. Next, we iterate over the array, and we calculate the actual sum of the elements. Finally, we subtract the actual sum from the expected sum, and the result will be the missing number in the array.

Here is the Python code for this approach:

class Solution:
def missingNumber(self, nums: List[int]) -> int:
n = len(nums)
expected_sum = n * (n + 1) // 2
actual_sum = sum(nums)
return expected_sum - actual_sum

This solution has a time complexity of O(n) because it involves iterating over the entire array once, and a space complexity of O(1) because we are not using any extra space to store data.

Another approach to solving this problem is by using the XOR operation. We know that XORing a number with itself will always result in 0. Also, XORing a number with 0 will result in the number itself. Using these properties, we can XOR all the elements in the array from 0 to n with each of the elements in the input array. The result will be the missing number in the array.

Here is the code for this approach:

class Solution:
def missingNumber(self, nums: List[int]) -> int:
missing_num = len(nums)
for i, num in enumerate(nums):
missing_num ^= i ^ num
return missing_num

This solution also has a time complexity of O(n) because it involves iterating over the entire array once, and a space complexity of O(1) because we are not using any extra space to store data.

Step by Step Implementation For Missing Number

public int missingNumber(int[] nums) {
    
    // we can use sum formula to calculate the missing number
    // (n*(n+1))/2
    
    int n = nums.length;
    int sum = (n*(n+1))/2;
    
    for(int i=0; i < nums.length; i++){
        sum -= nums[i];
    }
    
    return sum;
}

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        
        # initialize a set to store all the numbers in the input list
        num_set = set(nums)
        
        # initialize a variable to store the length of the input list
        n = len(nums)
        
        # iterate over all the numbers from 0 to n
        for num in range(n+1):
            
            # if the current number is not in the set, then it is the missing number
            if num not in num_set:
                return num

//Solution:

var missingNumber = function(nums) {
    
    //Create a variable to store the sum of all the numbers in the array
    let sum = 0;
    
    //Create a variable to store the length of the array
    let len = nums.length;
    
    //Loop through the array and add all the numbers together
    for(let i = 0; i < len; i++){
        sum += nums[i];
    }
    
    //Return the difference between the sum of all the numbers and the length of the array
    return len - sum;
    
};

class Solution {
public:
    int missingNumber(vector& nums) {
        // Initialize missing number to size of array
        int missing = nums.size();
        
        // Iterate through array and use XOR to cancel out matching indices and values
        for (int i = 0; i < nums.size(); i++) {
            missing ^= i ^ nums[i];
        }
        
        // The remaining value is the missing number
        return missing;
    }
};

public class Solution {
    public int MissingNumber(int[] nums) {
        // HashSet to keep track of which numbers have been seen
        HashSet seen = new HashSet();
        
        // Iterate through the array, adding each number to the HashSet
        for (int i = 0; i < nums.Length; i++) {
            seen.Add(nums[i]);
        }
        
        // Iterate through all numbers from 0 to the length of the array
        for (int i = 0; i <= nums.Length; i++) {
            // If the number is not in the HashSet, it is the missing number
            if (!seen.Contains(i)) {
                return i;
            }
        }
        
        // If no number is missing, return -1
        return -1;
    }
}