Suppose I have a std::vector A. This vector has only values in the range of 0 to A. size(), inclusive. For example, if there are 5 values in A, then the only values it can have are {0,1,2,3,4,5}, although not necessarily in that order. Duplicate values might be present too.

Obviously, at least one value is missing. Using O(n) time and O(n) space, where n is A. size(), determine which value(s) are missing from the vector.

The C++ code is explained below

Explanation:

#include<bits/stdc++.h>

using namespace std;

int main()

{

  vector<unsigned int>A;

  int n,i,num;

  cin>>n; // input no of elements

  for(i=0;i<n;i++)

  {

      cin>>num; // input elements

      A.push_back(num);

  }

  int hash[n+1]={0}; // Maintain a hash array.

  for(i=0;i<A.size();i++)

  {

      hash[A[i]]=1; //update hash array if element is present

  }

  cout<<"The missing elements are:-"<<endl;

  for(i=0;i<=n;i++)

  {

      if(hash[i]==0)

          cout<<i<<" ";

  }

}

Sample Input :-

5

3 3 3 4 5

Sample Output:-

The missing elements are:-

0 1 2