Lesson 99: ArrayInversionCount (Array Inversion Count)

Lesson 99: ArrayInversionCount
https://codility.com/programmers/lessons/14

I almost solved the problem, but I had to go out to dinner with my friends that day. So I googled so to not be frustrated during the dinner.

I had some intuition that this is about sorting, and possibly about heap-sort, but I didn't have the time to finish the last mile.

The problem I had is to fill this gap; this one is about sorting, and this is about merge-sort. If you don't parallelize merge sort and do it from the head of the data-area, you can easily check Q <R and A[Q] > A[R].

As I cheated by googling this time, I imposed myself to not use recursion for merge-sort.

Here is my answer that gives the 100% score. (Note that it is  'if (A[lpos] <= A[rpos])' as the problem A[Q] > A[R]').

#include<stdio.h>
#include <alloca.h>
#include <memory.h>



int solution(int A[], int N) 
{
    int cnt = 0;
    int memsize = sizeof(int) * N;
    int*work    = (int*)alloca(memsize);
    
    
    for (int blksize = 1; blksize < N; blksize *= 2){
        
        int lpos = 0;
        int rpos = blksize;

        //merge each blocks
        while(lpos <= N){
            int writebackpos = lpos;
            
            int lend = lpos + blksize;
            lend = lend >= N ? N : lend;
            
                        
            int rend = rpos + blksize;
            rend = rend >= N ? N : rend;

            //merge
            int wpos = 0;
            while (lpos < lend && rpos < rend){
                if (A[lpos] <= A[rpos]){
                    work[wpos++] = A[lpos++];
                }
                else {
                    work[wpos++] = A[rpos++];
                    cnt += lend - lpos;
                    if (cnt >=  1000000000){
                        return - 1;
                    }
                }
            }
            
            while (lpos < lend){
                work[wpos++] = A[lpos++];
            }

            while (rpos < rend){
                work[wpos++] = A[rpos++];
            }

            //write back
            memcpy(A + writebackpos, work, sizeof(int) * wpos);

            //proceed to the next block
            lpos = rpos;
            rpos = lpos + blksize;
        }

    }
   
    return cnt;
}

Lesson 99: StrSymmetryPoint (Str Symmetry Point)

Lesson 99: StrSymmetryPoint (Str Symmetry Point)
https://codility.com/programmers/lessons/14

This is a simple problem. We only scan from both ends.
If the scanning positions reached the same position, that's the
answer.

int solution(char *S) { int len = strlen(S); if (len % 2 == 0){ return -1; } int l = 0; int r = len - 1; while (l < r){ if (S[l] != S[r]){ return -1; } l++; r--; } return l; }

Lesson 99: BinaryGap (Binary Gap)

Lesson 99: BinaryGap
https://codility.com/programmers/lessons/14

Here is my first solution. It gives the 100% score.

I was wondering why the expected worst time complexity of this problem is O(log(N)). as 'int' is always 32 bit in this environment.

Yet, I guess it is because we can terminate the loop when there is no more binary gap can be found.

int solution(int N) 
{
    int max = 0;
    
    int mask = 0x80000000;

    int i = 0;

    //find the first 1.
    for (   ; i < sizeof(int) * 8; i++){
        int tmp = (N << i) & mask;
        if (tmp != 0){
            break;
        }
    }
    
    //no 1 found.
    if (i == sizeof(int) * 8){
        return 0;
    }
    
    //let's seek for the binary gap
    int cnt = 0;
    for (i = i +1; i < sizeof(int) * 8; i++){
        int tmp = (N << i) & mask;
        if (tmp == 0){
            cnt++;    
        }
        else {
            max = max < cnt ? cnt : max; 
            cnt = 0;
        }
    }
       
    return max;
}

And here is the version to terminate the loop when there is no more binary gap. This is the O(log(N)) version.

int solution(int N) 
{
    int max = 0;
    
    int i = 0;

    //find the first 1.
    for (   ; i < sizeof(int) * 8; i++){
        int tmp = (N >> i) & 1;
        if (tmp != 0){
            break;
        }
    }
    
    //no 1 found.
    if (i == sizeof(int) * 8){
        return 0;
    }
    
    //let's seek for the binary gap
    int cnt = 0;
    for (i = i +1; i < sizeof(int) * 8; i++){
        int tmp = (N >> i);
        if (tmp == 0){
            break;
        }
        
        tmp = tmp & 1;
        if (tmp == 0){
            cnt++;    
        }
        else {
            max = max < cnt ? cnt : max; 
            cnt = 0;
        }
    }
       
    return max;
}

And here is a shorter version.

int solution(int N) {
    
    int max = 0;
    int flg = 0;
    int cnt = 0;
    
    while (N > 0){
        if (N & 1 == 1){
            if (flg == 0){
                flg = 1;
            }
            else {
                max = max < cnt ? cnt : max;
            }
            cnt = 0;
        }
        else {
            cnt++;
        }
        N = N >> 1;
    }
    
    return max;
}

Lesson 99: OddOccurrencesInArray (Odd OccurrencesInArray)

Lesson 99:  OddOccurrencesInArray
https://codility.com/programmers/lessons/14

First, I thought how I can do this in the O(1) space complexity until I notice that there is only one element left unpaired in this problem.

If all the elements except one is paired, we can use xor for this problem and just one scanning is okay. Since A xor A = 0, and B xor 0 = B, if we keep on performing xor for all the values, the one left after iteration is the value unpaired.

int solution(int A[], int N) {
    
    int val = 0;
    for (int i = 0; i < N; i++){
        val ^= A[i];
    }
    
    return val;

}

Lesson 99: TreeHeight (Tree Height)

Lesson 99: TreeHeight
https://codility.com/programmers/lessons/14

We simply have to traverse the array by recursion.

void traverse(struct tree * T, int depth, int*max)
{
    if (depth > *max){
        *max = depth;    
    }
    
    if (T->l != NULL){
        traverse(T->l, depth + 1, max);
    }
    
    if (T->r != NULL){
        traverse(T->r, depth + 1, max);
    }
    
    return;
}

int solution(struct tree * T) 
{
    //handle an empty tree here.
    if (T == NULL){
        return - 1;
    }
    
    int max = 0;
    
    traverse(T, 0, &max);
    
    return max;
}

Lesson 15: MinAbsSum (Min Abs Sum)

Lesson 15: MinAbsSum
https://codility.com/programmers/lessons/16

Indeed, this problem is already described in the below PDF by Codility, so I simply show some C version of the solution. I think the last part to seek for the answer can be better to start from other direction (i.e., from sum / 2 to 0).

https://codility.com/media/train/solution-min-abs-sum.pdf

First, here I the slower version.

This gets the 100% correctness, but fails many tests for the performance score.

(1) The O(N^2 * max(abs(A))) solution

#include <alloca.h>
#include <memory.h>
#include <math.h>

int solution(int A[], int N) 
{
    int max = 0;
    int sum = 0;
    
    for (int i = 0; i < N; i++){
        A[i] = abs(A[i]);
        max = max < A[i] ? A[i] : max;
        sum += A[i];
    }

    int memsize = sizeof(int) * (sum + 1);
    int* dp = (int*)alloca(memsize);
    memset(dp, 0x00, memsize);
    
    dp[0] = 1;
    for (int i = 0; i < N; i++){
        for (int j = sum; j >= 0; j--){
            if (dp[j] == 1 && j + A[i] <= sum){
                dp[j + A[i]] = 1;    
            }
        }
    }
    
    int result = sum;
    for (int p = 0; p * 2 <= sum; p++){
        if (dp[p] == 1){
            int q = sum - p;
            int diff = q - p;
            result = diff < result ? diff : result; 
        }
    }
    return result;
}

(2) The O(N * max(abs(A))^2) solution

The faster version gives the 100% score.
So I think switching the algorithms to use depending on the N and Max would be a better strategy.

#include <alloca.h> #include <memory.h> #include <math.h> int solution(int A[], int N) { int max = 0; int sum = 0; for (int i = 0; i < N; i++){ A[i] = abs(A[i]); max = max < A[i] ? A[i] : max; sum += A[i]; } //the absolute values of A[] are between [0..100] int num_memsize = sizeof(int) * (max + 1); int* count = (int*)alloca(num_memsize); memset(count, 0x00, num_memsize); for (int i = 0; i < N; i++){ count[A[i]]++; } int dp_memsize = sizeof(int) * (sum + 1); int* dp = (int*)alloca(dp_memsize); //clear up with -1. memset(dp, 0xFF, dp_memsize); dp[0] = 0; for (int i = 1; i <= max; i++){ if (count[i] <= 0){ continue; } for (int j = 0; j <= sum; j++){ if (dp[j] >= 0){ dp[j] = count[i]; } else if (j >= i && dp[j - i] > 0){ dp[j] = dp[j - i] - 1; } } } int result = sum; for (int p = 0; p * 2 <= sum; p++){ if (dp[p] >= 0){ int q = sum - p; int diff = q - p; result = diff < result ? diff : result; } } return result; }

Lesson 15: NumberSolitaire (Number Solitaire)

Lesson 15: NumberSolitaire
https://codility.com/programmers/lessons/16

We already have solved a similar problem, Lesson 11:FibFrog.
Indeed, I was wondering why we have to use the dynamic programming concept  for this problem as it is scheduled in Lesson 15
http://codility-lessons.blogspot.tw/2015/03/lesson-11-fibfrog-fib-frog.html

Anyway, what we do is the almost the same as in the FibFrog problem. 
We prepare the array max_val[] and then initialize it with INT_MIN, which is smaller than the possible minimum value in the given conditions, except max_val[0], which is set the initial point we get when we start at A[0].

We begin from the position 0 and take the value at max_val[0]. Then, we add this point with the points we can obtain at each cell we can reach by the next jump and update the maximum value if it is larger than one that we obtained so far at the cell.

We repeat this until the cell we can perform the last jump (at the position N - 2, right before the goal).


This strategy gives the 100% score as below.

#include <alloca.h>
#include <limits.h>

int solution(int A[], int N) 
{
    int  memsize = sizeof(int) * N;
    int* max_val = (int*)alloca(memsize);
    
    //initialize the each cell with INT_MIN except the first one.
    max_val[0] = A[0];
    for (int i = 1; i < N; i++){
        max_val[i] = INT_MIN;
    }    
    
    //do dynamic programming for jump
    for (int pos = 0; pos < N - 1; pos++){
        
        //throw the dice (1-6)
        for (int j = 1; j <= 6; j++){
            //if out of range, neglect.
            int jump_pos = pos + j;
            
            //not to jump out of the range.
            if (jump_pos >= N){
                continue;
            }
            
            //update each cell's max value.
            int tmp = A[pos + j] + max_val[pos];
            max_val[jump_pos] = max_val[jump_pos] < tmp ? tmp : max_val[jump_pos];
        }
    }
    
    return max_val[N - 1];
}