vforbiedronka vforbiedronka - 26 days ago 6
C++ Question

Finding smallest subsequence of an array

I have an array e.g. {1,2,4,5,6}. I want my function to find biggest possible number X such that all numbers from 1,2,...,X-1 are in the array. In this case X=3. Numbers in an array could be from 0 to infinitty.

My attempt is:

int array(int* t, int r) {
int* a;
int m=0;
int i;

for(i=0;i<=r;i++){
a[i]=i;
if(a[i]==t[i])
m++;
}
return m;
}


I wanted to create an array from 1 to r, which is the length of an array, full of natural number i.e. {1,2,3...} . Then i wanted to compare it with the actual array t. If there is a match look for another one.

I have no idea why it does not work and how to fix it?

Anyway code does not work and i still have no idea how to fix this.

Still looking for an answer.

Answer

There are a number of issues with your code

int array(int* t, int r) {
    int* a;
    int m=0;
    int i;

    for(i=0;i<=r;i++){
        a[i]=i;
        if(a[i]==t[i])
            m++;
    }
    return m;
}
  • a is uninitialized, i.e. it does not point to valid memory allocated by your program. You need to do int *a = new int[r]. Don't forget to do delete a before your function returns
  • i should go up to r - 1 not r. So i < r rather than i <= r

Here is some pseudocode which outlines a possible method of solving this. The result is zero if it couldn't find a valid range to start from.

Pseudocode (Fast, thanks to Kenny Ostrom)

  • let curr = 0
  • let lookup = std::set<int>
  • insert all your elements into lookup
  • Starting from 0 to n where n is the size of your array of elements
    • [Loop]
      • If curr + 1 is not in lookup break out of loop
      • Else set curr to curr + 1
    • [Loop End]
  • Finally return curr + 1

Pseudocode (Fast depending on your sorting algorithm)

Similar to the above due to the fact that the range is sorted

  • Sort the array (std::sort is always a good option)
  • Set some variable curr to 0
  • Starting at a0 to an, where ai is an element of your array at index i
    • [Loop]
      • If curr + 1 is not equal ai then break out of the loop
      • Else set curr to ai
    • [Loop End]
  • Finally return curr + 1

Pseudocode (Slow)

  • Set some variable curr to 0
  • Starting at a0 to an, where ai is an element of your array at index i

    • [Loop]
      • Starting at aj to an where j = i
        • [Loop]
          • If curr + 1 is equal to aj then set curr to aj and break out of this loop
        • [Loop End]
        • If curr did not change, then break out of this loop
    • [Loop End]
  • Finally return curr + 1

Comments