Why is codility not giving me %100 correctness for this

user3613174 0
Viewed 91

The problem;

"return first positive integer that doesn't appear in vector"

My code below works for my test cases. However codility says Im only 40% correct (without giving reasons)

Here's my code, I dont see input arrays where this doesn't work.

/* return first non negative number that doesn't appear in vector e.g. -1,-4, 1, 3 ,2, 9, 10 -> return 4

e.g 1, 1, 2, 3, 4 -> returns 5

1) sort => -1 , -4, 1, 2, 3, 9 , 10 find first non negative number, ignore negatives. If all negatives , return 1;

  1. iterate starting from result of find_if 1 above.

  2. iterate until end or the next number is not next number e.g. 1,2,3,5 will stop at 3

  3. add 1 to get the smallest positive value not in input.

*/

int solution(vector<int>& A) {

    // I have a feeling max(int) is in play, the question doesn't specify what to do when
    // input = { 0,1,2,3,4 ... std::numeric_limits<int>::max() }

    cout << "Max int is " << std::numeric_limits<int>::max() << endl;
    std::sort(A.begin(), A.end());

    auto iter = find_if(A.begin(), A.end(), [=](int i)
        {
            return (i > 0);
        });

    if (iter == A.end())
    {
        return 1;
    }

    int result = *iter;
     
    while (iter < A.end() && ((*iter  - result) < 2))
    {
        result = *iter;
        ++iter;
    }

    result += 1;

    return result;
   
}
testing algorithm c++
1 Answers

The last part of your solution starts out wrong. It sets result to whatever positive number iter is pointing out:

    int result = *iter;  // what if *iter is 25?

It can never recover from that. I suggest that you simplify it by initializing result to 1 and just loop through the sorted vector until you find a number missing or you run out of numbers:

int solution(std::vector<int>& A) {
    int result = 1;

    std::sort(A.begin(), A.end());

    for (auto iter = find_if(A.begin(), A.end(), [](int i) { return i > 0; });
         iter != A.end();
         ++iter) 
    {
        if (*iter > result) break;      // `result` missing
        if (*iter == result) ++result;  // `result` found
    }

    return result;
}

A very similar algorithm would be to erase all numbers less than 1 from A before sorting. You can then use a range based for-loop to find the first missing number:

int solution(std::vector<int>& A) {
    int result = 1;

    std::erase_if(A, [](int i) { return i < 1; });
    std::sort(A.begin(), A.end()); // only positive numbers left here

    for(int value : A) {
        if (value > result) break;     // `result` missing
        if (value == result) ++result; // `result` found
    }

    return result;
}

or you could put the positive numbers in a std::set to get a container with unique and sorted numbers automatically which makes the search for missing numbers easier.

#include <set>

int solution(const std::vector<int>& A) {
    int result = 1;

    std::set<int> set;
    std::ranges::copy_if(A, std::inserter(set, set.end()),
                         [](int i) { return i > 0; });

    for(int value : set) {
        if (value != result) break; // `result` missing
        ++result;                   // `result` found
    }

    return result;
}
Ted Lyngmo0
Related