Table of Contents
Problem Statement
The Missing Number LeetCode Solution – “Missing Number” states that given an array of size n containing n distinct numbers between [0,n]. We need to return the number which is missing in the range.
Example:
Input: nums = [3,0,1]
Output: 2
Explanation:
- We can easily observe that all the numbers between [0,3] are present except the number 2.
- Hence, 2 is the missing number in the range [0,3].
Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8
Explanation:
- All the numbers except 8, are present in the array for the range [0,9].
- Hence, 8 is the missing number in the range [0,9].
Approach
Idea:
- There are multiple ways to solve this problem efficiently but, here we’ll discuss O(N) time and O(1) Space solution using Bit Manipulation.
- Let xo be the bitwise xor of all the numbers in the range [0,9] and all the elements of the input array. We can easily observe that all the elements except the missing number(frequency = 1) will have the frequency as 2.
- Also, we know that the bitwise xor of the number with itself is always zero. So, all elements having a frequency of 2, will yield bitwise xor as zero, and, the missing number will remain as it is(since frequency = 1).
- Finally, xo will store the missing number as our answer when we take bitwise xor of all numbers in the range [0,n] and all the elements of the input array.
Code
C++ code for Missing Number Leetcode Solution:
class Solution {
public:
int missingNumber(vector<int>& nums) {
int n = nums.size(),xo = n;
for(int i=0;i<n;i++){
xo^=i;
xo^=nums[i];
}
return xo;
}
};Java code for Missing Number Leetcode Solution:
class Solution {
public int missingNumber(int[] nums) {
int n = nums.length,xo = n;
for(int i=0;i<n;i++){
xo^=i;
xo^=nums[i];
}
return xo;
}
}Complexity Analysis for Missing Number Leetcode Solution
Time Complexity
The time complexity of the above code is O(n) since we run the loop exactly n times where n = size of the input array.
Space Complexity
The space complexity of the above code is O(1) since we’re using constant space.