Lesson 2: PermCheck (Perm Check)

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

この問題のcomplexityは下のようになっていますね。

最悪実行時間はO(N)ってことは、多分「ループはネストしてない」とかというお話で、最悪メモリ使用量がO(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).

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

で、下のコードになります。バケツ戦略？みたいなよくある手法です。

まず、配列B（入力と同じサイズ＝最悪メモリ使用量O(N))を用意して、そこにフラグを建てていきます。この配列Bでは、B[i] = 1の場合、iという数字が配列Aの中で見つかったという事になります。０なら見つからなかったという意味にします。

最初に配列Aをスキャンして配列Bにフラグをたてていきます。このときN以上の数字があったら、その時点でpermutationできてないので結果がわかっておしまい、そうでなければ配列Bのスキャン。

配列Bをスキャンしている間に０があったら、その数字は欠けているので、permutationになっていません。全部１だったら、出来てます、ってことですね。

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

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;

}

Lesson 1: PermMissingElem (Perm Missing Elem)

https://codility.com/programmers/lessons/
Lesson 1 - PermMissingElemの答えがこちらになります。

Expected worst-case complexityが O(1)なので、そこがちょっと難しい。

で、1から(N + 1)までの総和をとって、実際の配列内の要素の総和を引くといいということらしいので、そうすると100%の回答になる。

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

Complexity:

expected worst-case time complexity is O(N);

expected worst-case space complexity is O(1), beyond input storage 

(not counting the storage required for input arguments).

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

int solution(int A[], int N) 
{
    long sum = ((long)N + 1) * (N + 2) / 2;
    
    int i;

    for (i = 0; i < N; i++){
        sum -= A[i];
    }
    
    return sum;
}

Lesson 1: FrogJmp (Frog Jmp)

https://codility.com/programmers/lessons/
Lesson 1 - FrogJmpの答えがこちらになります。これは簡単。

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

Complexity:

expected worst-case time complexity is O(1);
expected worst-case space complexity is O(1).

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

int solution(int X, int Y, int D) {

    int distance = Y - X;

    return distance % D == 0 ? distance / D : distance / D + 1;

}

Lesson 1: Tape Equilibrium (Tape Equilibrium)

https://codility.com/programmers/lessons/
Lesson 1 - Tape Equilibriumの答えがこちらになります。

下のようにworst-case space complexityが O(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).

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

#include <stdlib.h>
int solution(int A[], int N) {

    //long is large enough for this problem.
    long sum = 0;  
    
    int i;    
    int *B = (int*)alloca(sizeof(int) * N);   

    //first, scan the elements from the tail to the head and
    //create an array of the running sums at the point    
    //(from the tail to the point).
    
    long runningSum = 0;    
    for (i = N - 1; i > 0; i--){        
        runningSum += A[i];        
        B[i] = runningSum;    
    }        
    
    //now, scan the array again, checking the difference.   
    runningSum = A[0];   
    long dif = abs(B[1] - runningSum);    
    
    for (i = 1; i < N - 1; i++){        
        runningSum += A[i];        
        long tmp = abs(B[i + 1] - runningSum);        
        if (tmp < dif){           
            dif = tmp;         
            
        }    
    }  
    
    return dif;
}

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

ところが、実際はこれexpected worst-case space complexityが
O(1)の問題ですね。

expected worst-case space complexity of O(N) 
expected worst-case space complexity of O(1)

当たり前ですが、ある場所で左側の総和＋右側の総和って全体の総和と同じ
ですよね。だから、必要なのは全体の総和だけで、いちいちメモリ確保して
そこまでの値しまっておく必要ないんですよね。

で、そういうコードが下になります。

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

これも１００％のスコアです。

int solution(int A[], int N) {
    
    long sum = 0;
    
    int i;
    
    //get the sum of all the elements.
    for (i = 0; i < N; i++){
        sum += A[i];
    }
    
    //check it with the running sums
    long rsum = A[0];
    sum -= A[0];
    
    long dif  = abs(sum - rsum); 
    for (i = 1; i < N - 1; i++){
        rsum += A[i];
        sum  -= A[i];
        long tmp = abs(sum - rsum);
        if (tmp < dif){
            dif = tmp;
        }
    }
    
    return dif;

}

個人的にはざっとみただけでも、Codilityのトレーニング問題では最悪のオーダーがまちがっているものが、ちらほらあります。

トレーニングでそういう感じだと、採用などで他人をテストするのに適切なサイトなのかという疑問が…