vforbiedronka - 1 year ago 66

C++ 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.

Answer Source

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.

- 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`

- If
- [Loop End]

- [Loop]
- Finally return
`curr + 1`

**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 a
_{0}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}

- If
- [Loop End]

- [Loop]
- Finally return
`curr + 1`

- Set some variable
`curr`

to`0`

Starting at a

_{0}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`

=`i`

- [Loop]
- If
`curr + 1`

is equal to a_{j}then set`curr`

to a_{j}and break out of this loop

- If
- [Loop End]
- If
`curr`

did not change, then break out of this loop

- [Loop]

- Starting at a
- [Loop End]

- [Loop]
Finally return

`curr + 1`