# Missing Number — Day 88(Python)

Today’s question is easy-tagged. It from Leetcode’s Daily Coding Challenge — March edition.

268. Missing Number

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.

Follow up: Could you implement a solution using only `O(1)` extra space complexity and `O(n)` runtime complexity?

Example 1:

Example 2:

Example 3:

Example 4:

Constraints:

• `n == nums.length`
• `1 <= n <= 104`
• `0 <= nums[i] <= n`
• All the numbers of `nums` are unique.

One way to solve this problem is by sorting the given array, then using a variable that starts from 0 and increments itself while checking if all the numbers are present in the array.

Let us look into the code snippet.

# Complexity analysis.

Time Complexity

Since we are sorting our array, the time complexity to sort is O(NlogN).

Space Complexity

Space complexity is O(1).

Is it possible to improve the time complexity? Can we use maybe some extra data structure to solve this problem?

We can use an array that is initialized with -1. What should the size of the array be? Since we are expected to have all the numbers from 0 to n, the size of the array should be n + 1, or in other words length of array + 1. After initialization, go through each number from the input array, these numbers will be the index in our extra array. In these indexes, replace -1 with the current index. Then go through the extra data structure and check if any of the indexes have -1. Those indexes with -1 are the missing numbers.

Let us look into the code snippet.

# Complexity analysis.

Time Complexity

Since we are just traversing through the array, the time complexity is O(N)

Space Complexity

Since we are using an extra data structure of size N, the space complexity is O(N).

Is there a way to improve the space complexity?

Bit manipulation is another way to solve this problem. I had to read through leetcode’s solution to understand this.

When we XOR a number with itself, we get 0 as output. Can we leverage this information? Since we are expected to have numbers from 0 to N, we can XOR each number with its index and look for missing number.

Let us look into the code snippet.

# Complexity analysis.

Time Complexity

Since we are just traversing through the array, the time complexity is O(N)

Space Complexity

Space complexity is O(1).

## More from Annamariya Tharayil

Software Engineer. Find me @ www.linkedin.com/in/annamariya-jt