Question

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.

Answer 1

The C++ code is explained below

Step-by-step 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