Lesson 1: TapeEquilibrium (Tape Equilibrium)

Here is my answer for Lesson 1 - Tape Equilibrium.

As the expected worst-case time/space complexity is as below,
it seems allowed to allocate some memory, so I used `alloca'…

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

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 code below gave me this score. 

#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;
}

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

However, I think the problem can be performed with the

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

The code below still scans the array twice, but do 
not waste the memory as above.

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

This also gives the score below.

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;
}