Task score : 100% -  Correctness : 100% ; Performance : 100%

Detected time complexity : O(N * log(log(N)))

Lesson 10 at app.codility.com/programmers

The solution and its explanation are given below. 

Category of Article : Technology | Computers and Software | Algorithm

Problem

A non-empty array A consisting of N integers is given. 

A peak is an array element which is larger than its neighbors. More precisely, it is an index P such that 0 < P < N − 1,  A[P − 1] < A[P] and A[P] > A[P + 1].

For example, the following array A: 

    A[0] = 1

    A[1] = 2

    A[2] = 3

    A[3] = 4

    A[4] = 3

    A[5] = 4

    A[6] = 1

    A[7] = 2

    A[8] = 3

    A[9] = 4

    A[10] = 6

    A[11] = 2

has exactly three peaks: 3, 5, 10. 

We want to divide this array into blocks containing the same number of elements. More precisely, we want to choose a number K that will yield the following blocks:

·         A[0], A[1], ..., A[K − 1],

·         A[K], A[K + 1], ..., A[2K − 1],

        ...

·         A[N − K], A[N − K + 1], ..., A[N − 1].

What's more, every block should contain at least one peak. Notice that extreme elements of the blocks (for example A[K − 1] or A[K]) can also be peaks, but only if they have both neighbors (including one in an adjacent block). 

The goal is to find the maximum number of blocks into which the array A can be divided.

Array A can be divided into blocks as follows: 

       - one block (1, 2, 3, 4, 3, 4, 1, 2, 3, 4, 6, 2), this block contains three peaks;

       - two blocks (1, 2, 3, 4, 3, 4) and (1, 2, 3, 4, 6, 2), every block has a peak.

       - three blocks (1, 2, 3, 4), (3, 4, 1, 2), (3, 4, 6, 2), every block has a peak. Notice in particular that the first block (1, 2, 3, 4) has a peak at A[3], because A[2] < A[3] > A[4], even though A[4] is in the adjacent block.

However, array A cannot be divided into four blocks, (1, 2, 3), (4, 3, 4), (1, 2, 3) and (4, 6, 2), because the (1, 2, 3) blocks do not contain a peak. Notice in particular that the (4, 3, 4) block contains two peaks: A[3] and A[5]. 

The maximum number of blocks that array A can be divided into is three.

Write a function: 

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

that, given a non-empty array A consisting of N integers, returns the maximum number of blocks into which A can be divided. 

If A cannot be divided into some number of blocks, the function should return 0.

For example, given: 

    A[0] = 1

    A[1] = 2

    A[2] = 3

    A[3] = 4

    A[4] = 3

    A[5] = 4

    A[6] = 1

    A[7] = 2

    A[8] = 3

    A[9] = 4

    A[10] = 6

    A[11] = 2

the function should return 3, as explained above. 

Write an efficient algorithm for the following assumptions:

·         N is an integer within the range [1..100,000];

·         each element of array A is an integer within the range [0..1,000,000,000].

Note

Integer Division

When a big integer is divided by a smaller integer, the quotient (answer) has a whole number part and a remainder. The remainder can be zero. With integer division, only the whole number is considered, and the remainder, is ignored. 

Also note that the smaller the divisor (K, for size of block) for any division operation, the bigger the quotient (number of blocks).

It has to be stressed that the start and end indexes of the list cannot be peaks, though peaks with the list can be at the start and the end of blocks. 

Brute Force Approach

The brute force approach begins by considering the whole dataset as one block. In this case the maximum number of blocks is 1, as long as the whole dataset has at least one peak. Next the dataset is divided into two equal parts (integer division). In this case the maximum number of blocks is 2, as long as each block has at least one peak. Next the dataset is divided into three equal parts (integer division). In this case the maximum number of blocks is 3, as long as each block has at least one peak.

This division continues until at least one block has no peak. With the given dataset above, the division will end at 4 blocks, because with 4 blocks, the first block has no peak; and the third block also has no peak. So the maximum number of blocks of equal size above is 3. It is not 4, because with 4 divisions, at least one block has no peak.

The reader should bear in mind that the maximum number of blocks is the divisor of the last accepted division; after which further divisions lead to at least one block without a peak. 

With this brute force approach, each element in a tentative block has to be scanned one-by-one to see if there is a peak.

It can be tedious and error-prone, to code the solution, the brute force way. So the brute-force solution is not addressed in this document. 

Better Solution but with some Limitations

The example dataset in the problem is:

    int B[] = {1, 2, 3, 4, 3, 4, 1, 2, 3, 4, 6, 2}; 

A set where 1 (as number of occurrence) is placed where a peak should be, and 0 is placed where there is no peak, is as follows:

    {0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0} 

The peak elements are for indexes 3, 5 and 10, which are 4, 4 and 6. The running peak count (sum) for the number of peaks, is as follows:

    int runPeakCount[] = {0, 0, 0, 1, 1, 2, 2, 2, 2, 2, 3, 3} 

At this point in this document, it is known that the answer is 3, for maximum number of same size blocks with at least one peak. N, the total number of elements in the list is 12. The block size is 4, from 12 ÷ 3.

Working backwards in the running-peak-counts list, 3 at index 11 minus 2 at index 7, gives 1. This means there is one peak in the last block from index 8 to 11 (inclusive). 2 at index 7 minus 1 at index 3, gives 1. This means there is one peak in the middle block (of 4 elements each, in each block) from index 4 to 7 (inclusive). 1 at index 3 minus 0 at index 1, gives 1. This means there is one peak, in the block from index 0 to 3 (inclusive). With the first block, the subtraction has to be made between 1 at index 3 and 0 at index 0, and not between 1 at index 3 and a value at index -1 that does not exist; in sympathy with the previous subtractions. The reader should not confuse between running sums and prefix sums. When this subtraction of 1 - 0 is done, to give 1, it will mean that there is one peak from index 0 to index 3 (inclusive - zero based indexing). Remember that there can be no peak at index 0 and at index 11 (the extreme ends), as they would have no neighbors. If the difference is 2, it means that there are two peaks in that block; if the difference is 3, it means that there are three peaks in that block; if the difference is 4, it means that there are four peaks in that block; and so on. 

So, by having a list of running-peak-counts, the maximum number of blocks with at least one peak, can be determined in this way (subtracting). However, how does one arrive at a block size of 3 for this example dataset, or the right block size for any other dataset?

The title for the lesson of this problem is Prime and Composite Numbers. So it should occur to the reader that the knowledge in the lesson (tutorial) is needed for this problem. Exactly what is needed, is the factors of N, which is equal to 12 for the example dataset. 12/12 = 1R0; 12/6 = 2R0; 12/4 = 3R0; 12/3 = 4R0; 12/2 = 6R0; 12/1 = 12R0. Remember that the divided blocks must be of the same size, and so the quotient should not have a remainder. 

The factors of 12 are: 1, 2, 3, 4, 6, and 12 itself. When the factor is 1 for number of blocks, the block size is 12 ÷ 1 = 12. When the factor is 2 for number of blocks, the block size for each of the blocks is 12 ÷ 2 = 6. When the factor is 3 for number of blocks, the block size for each of the blocks is 12 ÷ 3 = 4. When the factor is 4 for number of blocks, the block size for each of the blocks is 12 ÷ 4 = 3. When the factor is 6 for number of blocks, the block size for each of the blocks is 12 ÷ 6 = 2. When the factor is 12 for number of blocks, the block size for each of the blocks is 12 ÷ 12 = 1. Remember that the presence of a particular block size does not necessarily mean that, that block has at least one peak. Also, a block size of 1 cannot exist for this problem, because a peak needs two neighbors to be considered a peak.

Obtaining the factors is similar to obtaining the number of factors, as was taught in the lesson: Just push_back the factors into an array as they are obtained. After having a factor that is less than √N, obtain the bigger factor with N divided by the smaller counterpart. Push_back that too into the array. When N is a perfect square, do not the push_back the same two values of √N twice (push only once). After obtaining all the factors, sort ascending. 

After sorting, use the factors set and the running-peak-counts set, to determine the maximum number of blocks, where each block has at least one peak. Iterate from the smallest factor to the highest factor. The program is (read through the code and comments):

#include <stdio.h> 

int solution(int A[], int N) {    
    int rPeakCount=0;
    int runPeakCount[N];
    for (int i=0; i< N; i++)
        runPeakCount[i] = 0;    //cell zero will remain with the value zero.
    for(int i=1;i<N-1;i++){
        if ((A[i-1]<A[i])&&(A[i+1]<A[i])) {
            rPeakCount++;
        }
        runPeakCount[i] = rPeakCount;
    }
    runPeakCount[N-1] = rPeakCount;

    //the factors
    int factors[N];
    int p = 0;    //zero based position and no. of factors

    //obtain all factors in ascending order
    for (int i=1; i<=N; i++) {    
        if (N % i == 0) {
             factors[p] = i;
             p = p + 1;
        }
    }
 
    int noBlocks = 0;    //noBlocks is for maximum required
    for (unsigned int i=0; i<(p+1); i++) {    //no. of factors is p+1
        int K = N / factors[i];    //blockSize is K
        _Bool foundPeak = 0;    //reset foundPeak
        for (int j=0; j<N; j=j+K ) {    //increment with K
            int leftlimit;
            if (j == 0) leftlimit = 0;
            else leftlimit = j-1;
        
            if (runPeakCount[j+K-1] - runPeakCount[leftlimit] > 0) {
                foundPeak = 1;
            }
            else {
                foundPeak = 0; 
                 break;    //breaks from inner for-loop  
            }
        }
        if (foundPeak == 1)
            noBlocks = N / K;
        else if (foundPeak == 0)
            break;    //do not waste time handling the smaller block sizes
    }    
    
    return noBlocks;
}

int main() 
{ 
    int B[] = {1, 2, 3, 4, 3, 4, 1, 2, 3, 4, 6, 2};    //rPeakCount = {0, 0, 0, 1, 1, 2, 2, 2, 2, 2, 3, 3}
    int N = sizeof(B) / sizeof(B[0]);    //divide size of array by size of one (first) element
    int ret1 = solution(B, N);
    printf("%i\n", ret1);

    int C[] = {0, 1, 0, 0, 1, 0, 0, 1, 0};    //rPeakCount = {0 1 1 1 2 2 2 3 3 }
    N = sizeof(C) / sizeof(C[0]);
    int ret2 = solution(C, N);
    printf("%i\n", ret2);

    int D[] = {0, 1, 0, 0, 0};    //rPeakCount = {0 1 1 1 1}
    N = sizeof(D) / sizeof(D[0]);
    int ret3 = solution(D, N);
    printf("%i\n", ret3);

    int E[] = {0, 1, 0, 1, 0};    //rPeakCount = {0 1 1 2 2}
    N = sizeof(E) / sizeof(E[0]);
    int ret4 = solution(E, N);
    printf("%i\n", ret4);

    return 0; 
}

After scanning the running-peak-counts list completely, if each block has at least one peak, then the variable, foundPeak will be true. 

At app.codility.com/programmers the scoring and detected time complexity for this solution() function is:

    Task score : 81% -  Correctness : 66% ; Performance : 100%

    Detected time complexity : O(N * log(log(N))) 

Analysis (errors)

Despite the errors, the sample outputs are: 

    3

    3

    1

    1

and correct! 

How is the logic in the above solution() function? - During the inner for-loop execution, if foundPeak becomes false for any block (block-size), the inner for-loop breaks (stops execution). The outer for-loop at the bottom, does not note that number of blocks (noBlocks) as the maximum number of blocks at that stage. It instead uses the value of foundPeak of false, to break its own outer for-loop. Note that the value returned as the maximum number of blocks, is the previous noBlocks for the outer for-loop.

At the app.codility.com/programmers result, the Correctness Test for simple1 and simple2, each states that “got 2 expected 4”. This means that the required maximum number of blocks was never reached in each case. This is because, the inner for-loop detected false when the list was divided by three, and it was not supposed to do so (detect false). How can that happen? 

Consider a given list of:

    0, 7,  0, 7, 0, 0, 0, 0, 7, 0, 7, 0 

When this list is divided by 1, there is at least one peak in the whole block. When the list is divided by 2, it becomes

    0, 7, 0, 7, 0, 0,            0, 0, 7, 0, 7, 0 

There is still at least one peak in each block. If this division, was the previous division, then the maximum number of blocks (noBlocks) would be 2. If the whole list is further divided into 3 equal parts, the result would be,

    0, 7,  0, 7,            0, 0, 0, 0,            7, 0, 7, 0 

The middle block has no peak, and the value of 2 would be returned as the maximum number of blocks. Now, divide the list further into 4 equal parts, and the result becomes:

    0, 7,  0,            7, 0, 0,            0, 0, 7,            0, 7, 0 

When number of blocks (noBlocks) is 4, each block has at least one peak. This is the kind of error that is incorporated with the above solution() logic. 

The issue arose because the factors set was sorted ascending, and in the division process, the number of blocks was increasing from 1 and going higher. If the factors set is sorted descending, and in the division process, the number of blocks begin from N coming downwards, then the division at 4 blocks will not be skipped (to 2 blocks), because of the division at 3 blocks. This means the dividing starts with the largest number of blocks, where some blocks have no peaks. The dividing ends with the first set of blocks, when all the blocks have at least one peak.

Optimum Solution

The new program is (read through the code and comments, and note where the changes occur when compared with the previous program): 

#include <stdio.h> 

int solution(int A[], int N) {    
    int rPeakCount=0;
    int runPeakCount[N];
    for (int i=0; i< N; i++)
        runPeakCount[i] = 0;    //cell zero will remain with the value zero.
    for(int i=1;i<N-1;i++){
        if ((A[i-1]<A[i])&&(A[i+1]<A[i])) {
            rPeakCount++;
        }
        runPeakCount[i] = rPeakCount;
    }
    runPeakCount[N-1] = rPeakCount;

    //the factors
    int factors[N];
    int p = 0;    //zero based position and no. of factors

    //obtain all factors in descending order - change occurs here
    for (int i=N; i>=1; i--) {    
        if (N % i == 0) {
             factors[p] = i;
             p = p + 1;
        }
    }
 
    int noBlocks = 0;    //noBlocks is for maximum required
    for (unsigned int i=0; i<(p+1); i++) {    //no. of factors is p+1
        int K = N / factors[i];    //blockSize is K
        _Bool foundPeak = 0;    //reset foundPeak
        for (int j=0; j<N; j=j+K ) {    //increment with K
            int leftlimit;
            if (j == 0) leftlimit = 0;
            else leftlimit = j-1;
        
            if (runPeakCount[j+K-1] - runPeakCount[leftlimit] > 0) {
                foundPeak = 1;
            }
            else {
                foundPeak = 0; 
                 break;    //breaks from inner for-loop  
            }
        }
        //change occurs here
        if (foundPeak == 1) {    //arrived
            noBlocks = N / K;
            break;    //do not waste time handling the smaller factors
        }
    }    
    
    return noBlocks;
}

int main() 
{ 
    int B[] = {1, 2, 3, 4, 3, 4, 1, 2, 3, 4, 6, 2};    //rPeakCount = {0, 0, 0, 1, 1, 2, 2, 2, 2, 2, 3, 3}
    int N = sizeof(B) / sizeof(B[0]);    //divide size of array by size of one (first) element
    int ret1 = solution(B, N);
    printf("%i\n", ret1);

    int C[] = {0, 1, 0, 0, 1, 0, 0, 1, 0};    //rPeakCount = {0 1 1 1 2 2 2 3 3 }
    N = sizeof(C) / sizeof(C[0]);
    int ret2 = solution(C, N);
    printf("%i\n", ret2);

    int D[] = {0, 1, 0, 0, 0};    //rPeakCount = {0 1 1 1 1}
    N = sizeof(D) / sizeof(D[0]);
    int ret3 = solution(D, N);
    printf("%i\n", ret3);

    int E[] = {0, 1, 0, 1, 0};    //rPeakCount = {0 1 1 2 2}
    N = sizeof(E) / sizeof(E[0]);
    int ret4 = solution(E, N);
    printf("%i\n", ret4);

    return 0; 
}

At app.codility.com/programmers the scoring and detected time complexity for this solution() is: 

    Task score : 100% -  Correctness : 100% ; Performance : 100%

    Detected time complexity : O(N * log(log(N))

Thanks for reading.