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++) {
}

// 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;
}
}```

Scroll to Top

Top 100 Leetcode Practice Problems In Java

Get 30% Off Instantly!
[gravityforms id="5" description="false" titla="false" ajax="true"]