vforbiedronka vforbiedronka - 1 month ago 7
C++ Question

Finding missing number in an array

I want to have a function that would browse through the natural numbers array of any size ({0,1,2....}) and find a missing value.

What i mean is that if the array is e.g : {0,1,3,4,5} i want the function to return 2, if array is {1,3,0,4} i want the function to return 2 and so on...

My attempt is:

int missing(int* t, int r) {
int i;
int sum=0;
sum=(r+1)*(r+2)/2;
for(i=0;t[i];i++){
sum-=t[i];
}
return sum;
}


The idea was to first calculate the sum from 1 to n and than subtract from this sum each number in an array separately. However the program returns total sum without subtraction of the numbers in an array.

Why it is not working correctly?

Answer

Use condition i < r instead t[i]. First value of sequence is zero, therefore loop is not traversed

Moreover you can use optimized version of algorithm (unfortunately I don't have opportunity to test code -- it is just idea for only sorted array)

int res = 0;
for (int i = 0; i < r && t[i] == res; ++i, ++res) ;