find 3 missing numbers from a list of 97 unique

Asked Oct 23 '11 at 05:13

Active Oct 23 '11 at 06:01

Viewed 330 times

Possible Duplicate:
Easy interview question got harder: given numbers 1..100, find the missing number(s)

Given a list (or array) of 97 numbers, each number is unique and between 1 and 100. How to find three missing numbers from the list ? complexity of the algorithm ?

My solution:

 find3missing(int* array)
 {
 int newarray[100] = {0};

 For i = 0 to 99 
  ++newarray[array[i]] ; 

 For i = 0 to 99
If newarray[i] != 1
    Cout << “the missing number is ” << i+1 << endl ;
 }

 O(n).

Any better solutions ?

thanks

edited May 23 '17 at 10:34

Community

asked Oct 23 '11 at 05:13

user1002288

4,860
10
50
78

3

I don't think it's possible to do better than `O(n)` since you still have to look at all the elements. – Mysticial Oct 23 '11 at 05:15
Ya You must operate on all n numbers so O(n) is unavoidable – Neel Basu Oct 23 '11 at 05:35
Your solution needs O(n) additional space. It is possible to do better. – n. m. could be an AI Oct 23 '11 at 05:45
The first 99 should be 96, else you access array[97]...array[99] which don't exist. – James Waldby - jwpat7 Oct 23 '11 at 06:04

find 3 missing numbers from a list of 97 unique

0 Answers0