vforbiedronka vforbiedronka - 25 days ago 17
C++ Question

Subsequence of an array

This function calculates the largest possibly number x such that all number 1,...x-1 are in an array e.g. {1,3,2,5} -> 4. Function does not work for arrays with zero as It always then returns 1. Why is that?

int array(int* t, int r) {

for(int x=0;x<r;x++){

for(int y=0; y<r-1;y++){
if(t[y]>t[y+1]){
int temp=t[y+1];
t[y+1]=t[y];
t[y]=temp;
}
}
}
for (int i = 0; i != r; i++) {
if (t[i] != (i + 1)) {
return i + 1;
}
}
return r + 1;
}

Answer

When checking the sequence of sorted numbers, you check that t[i] == i+1, so if the ith element is at position i. This only works if your sequence starts with 1. Instead you should check that the i+1th element is the ith element +1, so

if (t[i]+1 != t[i+1]) {
  return t[i] + 1;
}
Comments