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