## Stripe Interview Question

Software Engineers**Country:**United States

This question is asking the first missing positive integer from the list of n integers. (Total n-1 integers given and return value should be an integer missing (m) from this list. So, it is implied that 1<=m<=n.

```
#include<iostream>
#include<vector>
using namespace std;
int missingInt(vector<int> v) {
int cnt=0, tmp=v[0],n=v.size(),i=0;
while(cnt<=n) {
if(v[i] != i+1 && v[i]<=n) {
tmp = v[v[i]-1];
v[v[i]-1] = v[i];
v[i]=tmp;
}
else i++;
cnt++;
}
int j=0;
for( j=0;j<n;++j)
if(v[j]!=j+1) return j+1;
return j+1;
}
int main() {
vector<int> v = {4,1,5,3}; // Don't sort it. Otherwise it will be n log(n).
int ret = missingInt(v);
cout<<ret;
return 0;
}
```

We traverse the array containing all positive numbers and to mark presence of an element x, we change the sign of value at index x to negative. We traverse the array again and print the first index which has positive value. In the following code, findMissingPositive() function does this part. Note that in findMissingPositive, we have subtracted 1 from the values as indexes start from 0 in C.

```
/* Find the smallest positive missing number
in an array that contains all positive integers */
int findMissingPositive(int arr[], int size)
{
int i;
// Mark arr[i] as visited by making arr[arr[i] - 1] negative.
// Note that 1 is subtracted because index start
// from 0 and positive numbers start from 1
for(i = 0; i < size; i++)
{
if(abs(arr[i]) - 1 < size && arr[ abs(arr[i]) - 1] > 0)
arr[ abs(arr[i]) - 1] = -arr[ abs(arr[i]) - 1];
}
// Return the first index value at which is positive
for(i = 0; i < size; i++)
if (arr[i] > 0)
// 1 is added because indexes start from 0
return i+1;
return size+1;
}
```

- Diego August 01, 2019