Lesson 2: PermCheck (Perm Check)

The expected worst-case time complexity of O(N) is likely to suggest that 'possibly no nested loop' and the expected worst-case space complexity O(N) is likely to suggest that 'we can allocate the memory for the temporary working area (or areas), the size of which is propositional to N'.

========================================================================

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).

========================================================================

The below code uses a simple 'bucket' strategy. We first allocate

the memory for an array B to store flags. In this array , Each element at the index 'i' is '1', if the number 'i' appears in the array A and otherwise '0'. 

So we put the flags into these buckets in the array B.

Then, we check the array B so that if we can find any '0', which means the lacking number in the expected permutation. If there is no '0' in the array B, it is a permutation.

The below code gives this test score.

================================================================================

int solution(int A[], int N) 

{

    int B[N];

    memset(B, 0x00, sizeof(B));

    int i;

    for (i = 0; i < N; i++){

        if (A[i] > N){

           return 0;

        }

        B[A[i] - 1] = 1;

    }

    

    for (i = 1; i < N; i++){

        if (B[i] == 0){

           return 0;

        }

    }

    

    return 1;

}