finding missing numbers from array using O(n) time and O(1) space [duplicate]

Question

This question already has answers here:

Easy interview question got harder: given numbers 1..100, find the missing number(s) given exactly k are missing (49 answers)

Closed 8 years ago.

We have an array of numbers from 1 to 100. Two numbers are missing. Finding those two numbers using O(n) time and O(1) space. Noted that those numbers in the array are not sorted. example : let there be an array [4, missing, 1, missing, 2] As you can see, the missing is 3 and 5. Assuming that the array of numbers from 1 to 5 and two number is missing. Actually, it is [4, 1, 2] Without 3 and 5.

so, i dont know how to solve this. could someone of you help me? my programming language is c++. here is the array:

{24, 44, 19, 92, 1, 18, 28, 50, 88, 5, 52, 11, 76, 39, 82, 85, 65, 93, 98, 4, 72, 94, 45, 59, 48, 46, 47, 67, 87, 99, 14, 70, 80, 25, 20, 22, 21, 41, 77, 73, 2, 13, 36, 6, 27, 81, 29, 62, 8, 35, 32, 49, 10, 100, 90, 78, 30, 34, 51, 9, 43, 58, 26, 33, 64, 15, 17, 57, 12, 56, 61, 79, 75, 97, 84, 42, 55, 83, 91, 86, 38, 89, 96, 74, 23, 7, 68, 60, 16, 66, 69, 53, 3, 71, 37, 63, 54, 95}

Answer 1

Sort your array, iterate over the array fields, compare to a counter i you increment at every step, if i is different from the field push_back(i) in a vector.