Just a few thoughts on how you might improve your algorithm as stated:

1. The question doesn't state that there will Always be a missing number. So might it be good (given that the first value is guaranteed to be 0 so array[0]==0) then if array[n] != n you have 'missing' values.
2. If we accept that we have missing values in that case, then the difference between n and the value stored in array[n] tells us how many 'missings' we have.

Those two bits of information would allow us to truncate your algorithm to:

1. Do no work if there are no missing values
2. Stop work as soon as it finds the requisite number of 'missings'.

Hope that is helpful?

Just a few thoughts on how you might improve your algorithm as stated:

1. The question doesn't state that there will always be a missing number. So might it be good (given that the first value is guaranteed to be 0 so array[0] == 0) then if array[n] != n you have 'missing' values.
2. If we accept that we have missing values in that case, then the difference between n and the value stored in array[n] tells us how many 'missings' we have.

Those two bits of information would allow us to truncate your algorithm to:

1. Do no work if there are no missing values.
2. Stop work as soon as it finds the requisite number of 'missings'.