Finding smallest subsequence of an array

Question

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.

Update: I did something like:

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;
}

However when in input array i have zero at some place e.g. {5,0,1,2} the function always, regardless of where the zero is placed returns 1. Why is that?

Array indices start from zero. Modify your for loop so that it becomes: for(i=0;i — mba12, Nov 07 '16 at 20:55
Your algorithm is simply wrong. It will work only if those numbers occupy the leftmost positions in the array, and are in sorted order. Do you want a solution that is slow but simple, or one that is fast but complicated? — Beta, Nov 07 '16 at 21:56
Are you doing a bucket sort, using massive memory to get fast runtime? You forgot to initialize a, so you're trying to store your numbers in undefined random places in memory. If that is your plan then you need to have two loops, one to build the lookup, and another to get the answer. — Kenny Ostrom, Nov 07 '16 at 22:19
Your second question asks why doesn't it work if you look for t[0] == 1, after sorting 0 into that spot. Because you sorted 0 into that spot, so it breaks your bad assumptions. — Kenny Ostrom, Nov 08 '16 at 14:10

score 5 · Accepted Answer · edited May 23 '17 at 12:24

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::unordered_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 (Kinda fast depending on your sorting algorithm)

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

Pseudocode (Slow)

Set some variable curr to 0
Starting at a₀ to a_n, where a_i is an element of your array at index i
- [Loop]
  - Starting at a_j to a_n where j = 0
    - [Loop]
      - If curr + 1 is equal to a_j then set curr to a_j 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

Why a in uninitialized? If it is initialized in identical manner to t ? — vforbiedronka, Nov 07 '16 at 22:08
@vforbiedronka it is uninitialized because you did not make it equal to anything. To initialize it you either need to create a new array and set `a` to point to that array or set `a` to point to an already created array. — smac89, Nov 07 '16 at 22:17
@vforbiedronka even better will be `int *a = new int[/*Enter the size you want here*/]`. See my updated answer — smac89, Nov 07 '16 at 22:19
I'll toss my pseudocode here since you covered the errors already. std::set lookup; for all number in the input array, lookup.insert(number); look for answer = 1 in lookup, increment or return answer. (the problem with doing a bucket style lookup table is you are space dependent on the value of the answer, not the size of the input, and you have to be able to grow it) — Kenny Ostrom, Nov 07 '16 at 22:35
I meant unordered set, my bad. Using std::set doesn't really give any advantage over sorting. Your quadratic search has a minor error in the pseudocode, consider {2, 1, 4}. — Kenny Ostrom, Nov 08 '16 at 01:00

Jarod42 · Answer 2 · 2016-11-07T22:27:24.273

2

You don't need extra array, you may just iterate until index mismatch your expectation:

int find_iota_end(const int* a, int size)
{
    std::sort(a, a + size); // if initial array is not sorted.
    for (int i = 0; i != size; ++i) {
        if (a[i] != (i + 1)) {
            return i + 1;
        }
    }
    return size + 1;
}

edited Nov 07 '16 at 22:27

answered Nov 07 '16 at 21:20

Jarod42

203,559
14
181
302

For an array {1,5,6,2,3} and size=5 this function returns 2 whereas it should return 4. – vforbiedronka Nov 07 '16 at 21:26
It was unclear that the array was not sorted, `std::sort(a, a + size);` would fix that. – Jarod42 Nov 07 '16 at 22:26

score 1 · Answer 3 · answered Nov 08 '16 at 14:32

Upon reflection, I think your original idea was pretty close to a good algorithm, if you fix the bugs, and completely ignore any value a[i] where that value is not in the range [1..r].

You must allocate actual memory for your second vector, and you need two independent loops. The first loop fills in the second vector, if the value is relevant. The second loop looks for the answer.

This gives you space O(n) because you only consider that many possible answers, and time O(n) because it just reads through length, twice.

Finding smallest subsequence of an array

3 Answers3

Pseudocode (Fast, thanks to Kenny Ostrom)

Pseudocode (Kinda fast depending on your sorting algorithm)

Pseudocode (Slow)