/*
  This is a demo task. (see MissingInteger in Developer Training)

  Write a function:

  class Solution { public int solution(int[] A); }

  that, given an array A of N integers, returns the smallest positive integer (greater than 0) that does not occur in A.

  For example, given A = [1, 3, 6, 4, 1, 2] ==> [1,1,2,3,4,6], the function should return 5.

  Given A = [1, 2, 3], the function should return 4.

  Given A = [−1, −3], the function should return 1.

  Write an efficient algorithm for the following assumptions:

  N is an integer within the range [1..100,000];
  each element of array A is an integer within the range [−1,000,000..1,000,000].  
*/

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
int solution(vector<int> &A) {
    int result = 0;
    
    sort(A.begin(), A.end());
    cout << "sorted array: "; for (auto i: A) {cout << i << " ";} cout << endl;    

    size_t index = 0;

    // interate over negative values
    while (index < A.size() && A.at(index) < 0)
        index++;

    // if all values are negative return 1
    if (index == A.size())
        return 1;

    // if the first positive value is greater than 1 return 1
    if (A.at(index) > 1)
        return 1;

    cout << "start index: " << index << endl;
    
    for (; index < A.size(); index++)
    {
        if (index < A.size() - 1)
        {            
            if (A.at(index+1) > A.at(index) + 1)
                return A.at(index) + 1;
        }
        else // index == A.size() - 1
            return A.at(index) + 1;
    }
    return result;
}
};


int main(void)
{
    vector<tuple<vector<int>,int>> testCases = {
        { {1,3,6,4,1,2}, 5 },
        { {-1,-3}, 1 },
        { {1,2,3}, 4 },
        { {-5,-10,-11,2,3}, 1 },
        { {-5,-10,-11,1,2,3,4}, 5 },
        { {-5,-10,-11,1,2,3,4,5,7,8,9}, 6 },
        { {-1,3,4}, 1 },        
    };

    for (auto tc: testCases)
    {
        Solution s;
        vector<int>& input = get<0>(tc);
        int expected = get<1>(tc);
        int result = s.solution(input);
        
        int width = 10;
        cout << setw(width) << "input: "; for (auto i: input) { cout << i << " "; } cout << endl;
        cout << setw(width) << "result: " << result << endl;
        cout << setw(width) << "expected: " << expected << endl;
        cout << (result == expected ? "passed" : "failed") << endl;        
        cout << "----------------------------\n";
    }
}