Lesson 2: MissingIntegers (Missing Integers)

https://codility.com/programmers/lessons/2
Lesson 2: Missing Integersの答えがこちらになります。

やり方として最初に浮かぶのは、ある値が見つかったかどうかわかるようにフラグたてておいて、後でチェックすることですね。　問題もO(N)のメモリ使用量で良いと言ってるので、簡単にNの大きさの配列を作ってしまいましょう。

このやり方でも、ちゃんとやろうとすると、一つの値につき、見つかった・見つかっていないの１ビットですむのですが、文句を言われなければそうはせず、単純にintとかで富豪的に試してしまいましょう。

最も小さい正の整数といわれているので、０以下は無視して良く、またNより大きい値があった場合は、必ずN以下にかけている数字が入ってきますからNより大きい値は無視していいですね。

1-Nまで全部見つかった場合は、当然N+1がないという答えでよいので、これで取りあえず実装してみましょう。

とりあえず１００％のスコアがでたので、これでよいということにしましょう。

--------------------------------
       the solution
--------------------------------

int solution(int A[], int N) 
{
    //prepare the flags
    int* flag = (int*)calloc(sizeof(int), N);
    
    //iterate the given array A.
    int i;
    for (i = 0; i < N; i++){
        //we can neglect the value below 1 or larger than N.
        if (A[i] <= 0 || A[i] > N){
            continue;
        }
        //turn on the flag. this is the zero-indexed array.
        //so give -1 as the offset.
        flag[A[i] - 1] = 1;
    }
    
    //if there is no positive integer lacking between 1 - N,
    //the answer should be N + 1.
    int ans = N + 1;
    //found the minimum integer that is not found in the array A.
    for (i = 0; i < N; i++){
        if (flag[i] == 0){
            //the answer is (the index + 1). (we have -1 offset).
            ans = i + 1;
            break;
        }
    }
    
    //free the allocated memory space.
    free(flag);
    
    return ans;

}