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.

Question

Amanda

Computers & Technology

10 June, 01:16

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.

+4

Answers (1)

Know the Answer?

Virginia Ibarra · Answer 1

The C+ + code is explained below

Explanation:

#include

using namespace std;

int main ()

{

vectorA;

int n, i, num;

cin>>n; / / input no of elements

for (i=0; i
{

cin>>num; / / input elements

A. push_back (num);

}

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

for (i=0; i
{

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

}

cout<<"The missing elements are:-"<
for (i=0; i<=n; i++)

{

if (hash[i]==0)

cout<
}

}

Sample Input : -

5

3 3 3 4 5

Sample Output:-

The missing elements are:-

0 1 2