# Codility ‘MissingInteger’ Solution

##### Short Problem Definition:

Find the minimal positive integer not occurring in a given sequence.

MissingInteger

##### Complexity:

expected worst-case time complexity is O(N);

expected worst-case space complexity is O(N)

##### Execution:

You only need to consider the first (N) positive integers. In this specification 0 does not count as a valid candidate! Any value that is below 1 or above N can be ignored.

##### Solution:
```def solution(A):
seen = [False] * len(A)
for value in A:
if 0 < value <= len(A):
seen[value-1] = True

for idx in xrange(len(seen)):
if seen[idx] == False:
return idx + 1

return len(A)+1
```

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

• FatTailBlackSwan

Value can be any signed (32bit) int, no?

• FatTailBlackSwan

Only checking up to N is the key insight. Thank you!

• han

I have implemented slightly different logic which might be a bit faster:

def solution(A):
newA= [x+1 for x in A]+[1]
diff=set(newA)-set(A)
diff=filter(lambda a: a>0, diff)
#diff=filter(lambda a: a>0, diff)
result=min(diff)
return result

• David

Can anybody tell me why my solution fails on the last performance test (chaotic + many -1, 1, 2, 3)?

def solution(A):
for e in A[:]:
if e <= 0:
A.remove(e)
A = sorted(list(set(A)))
for i in range(len(A)):
if i+1 != A[i]:
return i + 1
return len(A)+1

• David

Can anybody tell me why my solution fails in the last performance test (chaotic + many -1, 1, 2, 3)?

def solution(A):
for e in A[:]:
if e <= 0:
A.remove(e)
A = sorted(list(set(A)))
for i in range(len(A)):
if i+1 != A[i]:
return i + 1
return len(A)+1

• sorted takes O(N*log(N)) time, they expect a (single/multi)-pass O(N) solution.

• Jon Williamson

C# solution using a HashSet
HashSet h = new HashSet();

foreach (int val in A)
if (val > 0)

int minpostive = 1;

foreach (int val in h)
{
if (val==minpostive)
do
{
minpostive++;
}
while (h.Contains(minpostive));
}

return minpostive;

• A JavaScript solution (100%):

``` function solution(a) { const length = a.length; const map = Array(length).fill(false); for (let i = 0; i < length; i++) { const item = a[i]; if (item length) { continue; } map[item - 1] = true; } for (let i = 0; i < length; i++) { if (!map[i]) { return i + 1; } } return length + 1; }```

``` ```

```assert.strictEqual(solution([2, 4, 5]), 1); ```

• Tanuj Sharma
• M. Rahil Rafiq
• Marcin Gola

Here is my solution(100% ranked) in C++

using namespace std;
#include

int solution(vector &A) {
int max = A[0];
for( size_t i = 0; i < A.size(); ++i )
{
if( max < A[i] )
max = A[i];

}
if( max <= 0 )
return 1;

vector range(max +1 );
for( size_t i = 0; i 0 )
range[A[i]-1] = 1;
}
for( size_t i = 0; i < range.size();++i )
{
if( !range[i])
return i+1;
}
return max;
}