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のトレーニング問題では最悪のオーダーがまちがっているものが、ちらほらあります。

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