MissingInteger

1. MissingInteger

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

Write a function:

int solution(vector<int> &A);

that, given a non-empty zero-indexed array A of N integers, returns the minimal positive integer that does not occur in A.

For example, given:

  A[0] = 1    
  A[1] = 3    
  A[2] = 6
  A[3] = 4    
  A[4] = 1    
  A[5] = 2

the function should return 5.

Assume that:

• N is an integer within the range [1..100,000];
• each element of array A is an integer within the range [−2,147,483,648..2,147,483,647].

Complexity:

• expected worst-case time complexity is O(N);
• expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.

Copyright 2009–2014 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

// you can write to stdout for debugging purposes, e.g. // printf("this is a debug message\n"); #include <algorithm> int solution(vector<int> &A) { // write your code in C++11 sort ( A.begin(), A.end() ); int result = 0; if ( *(A.begin()) > 1 ) result = 1; else if ( *(A.end()-1) <= 0 ) result = 1; else { int beforeValue = 0; for ( vector<int>::iterator it = A.begin(); it < A.end(); it++ ) { if ( *it <= 0 ) continue; else if ( *it > beforeValue+1 ) { result = beforeValue+1; break; } beforeValue = *it; } if ( beforeValue == 0 ) result = 1; else if ( beforeValue == *(A.end()-1) ) result = *(A.end()-1) + 1; } return result; }