Lesson 8: Peaks (Peaks)

Lesson 8: Peaks
https://codility.com/programmers/lessons/8

First, we find the peeks in the array A and store their index to another array.

If no peeks are found, we return 0. If there is any peek, we start checking from the possible maximum number of blocks=the number of the peeks (each block must contains at least one peek).


This strategy gives the 100% score.

#include <alloca.h>

int solution(int A[], int N) 
{
    //we need at least 3 elements to have a peek.
    if (N < 3){
        return 0;
    }

    //we will never have the number of peeks larger than N / 2.
    int *peeks = (int*)alloca(sizeof(int) * (N / 2));
    int peek_cnt = 0;
    
    //find peeks
    int i;
    for (i = 1; i < N - 1; i++){
        if (A[i - 1] < A[i] && A[i] > A[i + 1]){
            peeks[peek_cnt++] = i;
        }
    }
    
    //if there is no peek, return 0
    if (peek_cnt == 0){
        return 0;
    }
    
    //let's check from the block of the possible maxim number of blocks.

    //as we have at least one peek, we can say the minimum number of blocks 
    //that meets the given condition is 1.
    int maxdiv = 1; 
   
    for (i = peek_cnt; i > 0; i--){
        if (N % i != 0){
            continue;
        }
        
        //let's check if this number satisfies the conditon.
        int elems_for_each_block    = N / i;
        int next_block_end          = elems_for_each_block;

        int pidx = 0; //the index of the peek to check 
        int flg  = 1; //assume the number satisfies the condition first.

        while(1){
            //check if this block contains any peek.
            if (pidx >= peek_cnt || next_block_end <= peeks[pidx]){
                //no peeks detected, this is not a right choice.
                flg = 0;
                break;
            }
            
            //skip the peeks within the current block.
            while(pidx < peek_cnt && peeks[pidx] < next_block_end){
                pidx++;
            }

            next_block_end += elems_for_each_block;
            if (next_block_end > N){
                break;
            }
        }
        
        //at least one peek is contained in every block.
        if (flg){
            maxdiv = i;
            break;
        }  
    }
    
    
    return maxdiv;
}

I googled and found some people implemented a more efficient algorithm using the prefix sum. Instead of keeping the index of the peeks, they prepare another array that contains the prefix sum of the number of peeks found so far in the array A at the same index.

This strategy facilitate to check if the block size that is currently being examined satisfies the given condition or not.

This strategy also gives the 100% score.

#include <alloca.h>

int solution(int A[], int N)
{
    //for N < 3, there is no peek.
    if (N < 3){
        return 0;
    }

    //make the prefix sum of the number of the peeks at the index.
    int* peek_cnt_prefix_sum = (int*)alloca(sizeof(int) * N);
    
    peek_cnt_prefix_sum[0] = 0;
    int i;
    for (i = 1; i < N - 1; i++){
        peek_cnt_prefix_sum[i] = peek_cnt_prefix_sum[i - 1];
        if (A[i - 1] < A[i] && A[i] > A[i + 1]){
            peek_cnt_prefix_sum[i]++;
        }
    }
    
    peek_cnt_prefix_sum[N - 1] = peek_cnt_prefix_sum[N - 2];

    //no peek found.
    if (peek_cnt_prefix_sum[N - 1]  == 0){
        return 0;
    }
    
    int maxdiv = 1;
    for (i = peek_cnt; i > 0; i--){
        if (N % i != 0){
            continue;
        }
        
        int elems_for_each_block = N / i;
        
        //keep on checking
        int flg = 1; //assume this divisor of N satisfies the condition.

        int next_block_end = elems_for_each_block - 1;
        int current = peek_cnt_prefix_sum[0];
        while(next_block_end < N){  
            
            int next = peek_cnt_prefix_sum[next_block_end];
            //no peeks found between current and next.
            if (current >= next){
                flg = 0;
                break;
            }
            current = next;
            next_block_end += elems_for_each_block;
        }
        
        //if this divisor of N satisfied the condition,
        //it is the answer.
        if (flg){
            maxdiv = i;
            break;
        }
    }
    
    return maxdiv;
}

Lesson 8: CountFactors (Count Factors)

Lesson 8: CountFactors
https://codility.com/programmers/lessons/8

This is a easy problem. As the factors are paired except when the factor is equal to sqrt(N), we only have to check from 1 to sort(N). When the value is a factor, then increment the counter by 2. Yet when sqrt(N) is also a factor, we shouldn't count it twice. So we decrement 1 before returning the answer.

This strategy gives the 100% score.

int solution(int N) {
    
    int cnt = 0;
    
    int i;
    double sqrtN = sqrt(N);
    
    for (i = 1; i <= sqrtN; i++){
        if (N % i == 0){
            cnt += 2;
        }
    }
    
    //to avoid the sqrt(N) to counted twice.
    if (sqrtN == (int)sqrtN){
        cnt--;
    }
    
    return cnt;
}

Lesson 8: MinPerimeterRectangle (Min Perimeter Rectangle)

Lesson 8: MinPerimeterRectangle
https://codility.com/programmers/lessons/8

The simplest solution is to check all the possible values for a and b.
Yet, since a * b = N, we only have to check the values less than sqrt(N). 

This solution can give us the 100% score.

#include <math.h> int solution(int N)
{      int a;

    int sqrtN = sqrt(N);      int min = 2147483647; //the initial value for the min (INT_MAX).

    for (a = 1; a <= sqrtN; a++){          if (N % a == 0){
            int b = N / a;
            min = a + b < min ? a + b : min;
        }
    }
    
    return min * 2; }


However, the above code is not very efficient.

It is better to check the value of a, decrementing from sqrt(N) to 1, and finish checking right when we find some value for 'a' that is N % a == 0, and return (a * N / a) * 2. (note that N / a = b)


Let's think of below.

First we assume 1 <= x < y <= sqrt(N) . Both x and y are integer. (NOTE: this assumes 1 < N, which is a little different from the problem that assume 1 <= N <= 1,000,000,000).

what we want to know is if the following is true.

2 * (y + N / y) < 2 * (x + N / x)

The above can be rewritten as follows.

(y + N / y) < (x + N / x)

(y + N / y) - (x + N / x) < 0

(y - x) + (N / y - N / x) < 0

(y - x) < -(N / y - N / x)

(y - x) < -N / y + N / x

(y - x) < N / x - N / y

(y - x) < Ny - Nx / xy

(y - x) < N(y - x) / xy

1 < N / xy

since 1 <= x < y <= sqrt(N), 0 < xy < N. (even when y is equal to sqrt(N), x is smaller, so xy is always less than sqrt(N) * sort(N) = N.) Then above 1 < N / xy is true.

This means, if N is larger, the perimeter can be minimized when Y is the largest possible value that is less than or equal to sqrt(N)

For N = 1, obviously, there s only value for 'a' such that 1 <= 'a' <= sqrt(N) is 1.

So we always can start checking from the integer value 'a' from the sqrt(N) to 1 and when we met the first value that has the integer value 'b', which is b = N % a, the 'a' and 'b' gives the minimum value.

This strategy gives the 100% score, too.

#include <math.h> int solution(int N)
{      int a;
    int sqrtN = sqrt(N);

    for (a = sqrtN; a >= 1; a--){
        if (N % a == 0){
            break;
        }
    }

    return (a + N / a) * 2;
}

Lesson 7: MaxDoubleSliceSum (Max Double Slice Sum)

Lesson 7: MaxDoubleSliceSum
https://codility.com/programmers/lessons/7

This is yet another max slice problem.
The trick is to compute the maximum ending at each index for the left-side slice and the right-side slice first. Then, we move Y from 1 to N -2, scanning the max values for the left-side slice and the right-side slice at the index.

This strategy gives the 100% score.

#include <alloca.h>

int solution(int A[], int N) 
{
    if (N <= 3){
        return 0;
    }
    
    int* max_ending_l = (int*)alloca(sizeof(int) * N);
    int* max_ending_r = (int*)alloca(sizeof(int) * N);
     
    int i;
   
    //the max ending at the index from the left.
    max_ending_l[0] = 0;
    for (i = 1; i < N - 1; i++){
        int tmp = max_ending_l[i - 1] + A[i];
        max_ending_l[i] =  tmp < 0 ? 0 : tmp;
    }
    
    //the max ending at the index from the right.
    max_ending_r[N - 1] = 0;
    for (i = N - 2; i > 0; i--){
        int tmp = max_ending_r[i + 1] + A[i];
        max_ending_r[i] = tmp < 0 ? 0 : tmp;;
    }
    
    //then move Y to find the maximum double slice sum
    int max = 0;
    for (i = 1; i < N - 1; i++){
        int tmp = max_ending_l[i - 1] + max_ending_r[i + 1];
        if (max < tmp){
            max = tmp;
        }
    }
    
    return max;
}

Lesson 7: MaxSliceSum (Max Slice Sum)

Lesson 7: MaxSliceSum
https://codility.com/programmers/lessons/7

This is another max slice problem. 

The difference from the original cordiality reading material Open reading material (PDF) is that the slice can not be empty.

So if the max value of the slice that can end at the current position is smaller than the value at the current position, we take the later. (note that in the original version in the open reading material uses '0' instead, as the slice can be empty).

This solution gives the 100% score.

int solution(int A[], int N)
{   
    int max_ending = A[0];
    int max_slice  = A[0];

    int i;
   
    for (i = 1; i < N; i++){
        int tmp = max_ending + A[i];
        max_ending = tmp > A[i] ? tmp : A[i];
        max_slice  = max_slice < max_ending ? max_ending : max_slice;
    }
    
    return max_slice;
}

Lesson 7: MaxProfit (Max Profit)

Lesson 7: MaxProfit
https://codility.com/programmers/lessons/7

This problem indeed can be translated as a `max-slice' problem.

Notice that the profit/loss in two consecutive days is the price difference between these days. If we buy the stock at the first day and then sell it on the second day, the profit/loss of these two days is the price difference between these days.

Now let's think that we buy the stock at the first day and then sell it on the third day. The profit/loss between these two days is the price difference between these days. However, it can be also considered that the profit/loss between the first day and the third day is the price difference between the first day and the second day + the price difference between the second day and the third day.

So this problem can be translated to find the max-profit from the sequence of the price differences between a day and its next day.

This strategy gives the 100% score.

int solution(int A[], int N) 
{
    int max_ending = 0;
    int max_slice  = 0;

    int i;
    
    for (i = 1; i < N; i++){
        int diff = A[i] - A[i - 1];
        int tmp = max_ending + diff;
        max_ending = tmp < 0 ? 0 : tmp;
        max_slice  = max_slice < max_ending ? max_ending : max_slice;
    }

    return max_slice;
}

Lesson 6: Dominator (Dominator)

Lesson 6: Dominatorhttps://codility.com/programmers/lessons/6

This solution also utilizes the O(N) algorithm to find a leader described in the reading material that Codility provides. First read it briefly.
Open reading material (PDF)

Indeed, the definition of 'dominator' in this problem is the same as  'leader'. So we can use the same algorithm as the previous problem of `equi leader' 
(http://codility-lessons.blogspot.tw/2015/02/lesson-6-equileader.html)

This gives the 100% score as below.

#include <alloca.h>

int solution(int A[], int N) {
    
    //first find the leader and count its occurances.
    //as all the values on the stack will be the same,
    //we only have to keep one value.
    int sp = 0;
    int candidate = 0;
    
    int i;
    for (i = 0; i < N; i++){
        if (sp == 0){
            sp++;
            candidate = A[i];
            continue;
        }
        
        if (candidate == A[i]){
            sp++;
        }
        else {
            sp--;
        }
    }
    
    //if there is no dominator, return -1
    if (sp == 0){
        return -1;
    }
    
    //now we check if the candidate value is really a dominator
    int cnt = 0;
    for (i = 0; i < N; i++){
        if (A[i] == candidate){
            cnt++;
        }
    }
    
    //if there is no dominator, return -1.
    if (cnt <= N / 2){
        return -1;
    }
    
    //now we have a leader.
    int dominator = candidate;
  
    
    //let's find the first dominator in the array
    for (i = 0; i < N; i++){
        if (A[i] == dominator){
            return i;
        }
    }
    
    //the code won't reach here since we have a dominator. 
    return -1;
}

However, it should be noted that we don't have to scan the array after finding a dominator; we can return any of the place where the dominator is found, returning the last index is also okay.

#include <alloca.h>

int solution(int A[], int N) {

    

    //first find the leader and count its occurances.

    //as all the values on the stack will be the same,

    //we only have to keep one value.

    int sp = 0;

    int candidate = 0;

    int lastIndex = 0;

    

    int i;

    for (i = 0; i < N; i++){

        if (sp == 0){

            sp++;

            candidate = A[i];

            lastIndex = i;

            continue;

        }

        

        if (candidate == A[i]){

            sp++;

            lastIndex = i;

        }

        else {

            sp--;

        }

    }

    

    //if there is no dominator, return -1

    if (sp == 0){

        return -1;

    }

    

    //now we check if the candidate value is really a dominator

    int cnt = 0;

    for (i = 0; i < N; i++){

        if (A[i] == candidate){

            cnt++;

        }

    }

    

    if (cnt > N / 2){

        return lastIndex;

    }

    

    //if there is no dominator, return -1

    return -1;

}