vforbiedronka - 1 year ago 75
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.

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`

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download