Skip to content
Missing Number in Array LeetCode

Find Missing Number in Array LeetCode

Missing Number LeetCode, from the given array we have to find the missing numbers and we were asked to solve this with O(1) extra space complexity i.e constant space and O(n) runtime complexity. This means that we should not use extra space, it should be constant.

Input: [0,3,1,4]
Output: 2

Input: [2,1,4,6,7,5,9,0,2]
Output: 8

Description

Some important points to consider

  1. The array is NOT sorted
  2. One number is missing
  3. No extra memory, constant space
  4. We have to use only one loop, a single iteration

Solution Explanation

So we have an array of numbers of length n and we have to find the missing number, the problem is very easy if the array was sorted but it isn’t.

This can be easily solved using XOR, so basically, XOR deals with bit manipulation at the binary level. One thing you need to know is XOR of the same numbers cancel each other if you are still confused test some numbers using this XOR calculator

Now we use a loop where i=0 to i<length of array and

missing = missing ^ i ^ a[i-1]

where missing=0 and a[] is our array and the loop goes like this

Input: [0,3,1,4]
for(i=1;i<=4;i++)
missing = 0^1^0 = 1
missing = 1^2^3 = 0
missing = 0^3^1 = 2
missing = 2^4^4 = 2

Code for Missing Number LeetCode C++

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        int x = 0;
        for(int i=1;i<=n;i++)
            x = x ^ i ^ nums[i-1];
        return x;
    }
};

Conclusion

Link to Problem Missing Number LeetCode, Though it is a bit difficult in the beginning to understand XOR, it is very useful when dealing with similar problems like finding missing numbers. This post is part of my #30DaysChallenge to write a blog post every day on what I learn.

Happy Coding~ Abhiram Reddy

Tags: