Missing Number Leetcode Solution

Difficulty Level Easy
Frequently asked in Adobe Amazon Apple Bloomberg Cisco Facebook Goldman Sachs Google Intel Microsoft Nvidia Oracle PayPal Salesforce
Array Bit Manipulation Dynamic Programming Hash Maths SortingViews 7629

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:

Missing Number Leetcode Solution

 

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:

  1. 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.
  2. 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.
  3. 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).
  4. 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.

Reference: https://en.wikipedia.org/wiki/Bit_manipulation

Translate »