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;

}

Lesson 1: PermMissingElem (Perm Missing Elem)

As the expected worst-case space complexity is O(1), this problem is made a bit harder.

The strategy is to computer the expected sum when there is no lacking first, then subtract the actual sum you obtain from it.

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

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)

This one is quite easy.
====================================================

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