Problem

You are given N counters, initially set to 0, and you have two possible operations on them:

        increase(X) - counter X is increased by 1,
        max counter - all counters are set to the maximum value of any counter.

A non-empty array A of M integers is given. This array represents consecutive operations:

        if A[K] = X, such that 1 ≤ X ≤ N, then operation K is increase(X),
        if A[K] = N + 1 then operation K is max counter.

For example, given integer N = 5 and array A such that:

    A[0] = 3
    A[1] = 4
    A[2] = 4
    A[3] = 6
    A[4] = 1
    A[5] = 4
    A[6] = 4

the values of the counters after each consecutive operation will be:

    (0, 0, 1, 0, 0)
    (0, 0, 1, 1, 0)
    (0, 0, 1, 2, 0)
    (2, 2, 2, 2, 2)
    (3, 2, 2, 2, 2)
    (3, 2, 2, 3, 2)
    (3, 2, 2, 4, 2)

The goal is to calculate the value of every counter after all operations.

Assume that the following declarations are given:

    struct Results {
      int * C;
      int L; // Length of the array
    };

Write a function:

    struct Results solution(int N, int A[], int M);

that, given an integer N and a non-empty array A consisting of M integers, returns a sequence of integers representing the values of the counters.

Result array should be returned as a structure Results.

For example, given:

    A[0] = 3
    A[1] = 4
    A[2] = 4
    A[3] = 6
    A[4] = 1
    A[5] = 4
    A[6] = 4

the function should return [3, 2, 2, 4, 2], as explained above.

Write an efficient algorithm for the following assumptions:

        N and M are integers within the range [1..100,000];
        each element of array A is an integer within the range [1..N + 1].

Note:

From the question, "N counters" means N cells in the count array.

This problem is in the chapter of Counting Elements. A typical counting elements problem has array A from which a count array is obtained, where the value of each index in the count array is the number of occurrences of the index as value in the A array. The A array given above is:

    A = {3, 4, 4, 6, 1, 4, 4}

With that, the normal count array becomes:

Which is also written as:

    count = {0, 1, 0, 1, 4, 0, 1}

However, that is not the result wanted. What is wanted as return array, is the count array,

    count = {3, 2, 2, 4, 2}

where there is no value for the index 0, and from the following conditions:

        if A[K] = X, such that 1 ≤ X ≤ N, then operation K is increase(X),
        if A[K] = N + 1 then operation K is max counter.

        where K is the index variable, and "increase(X)" means increment (increase by 1) the value of the index, 
        X in the count array. Remember that each value in the count array is initialized to 0, at the start.

With the example data above, the maximum possible value in A has to be N, which is the length of the given A array. For the above case N = 5.

There is a nuance in the naming of variables in this chapter. In algorithm, m normally refers to the maximum value in array A and the length of the count array. However, in this problem, m (actually uppercase m) refers to the length of array A and N refers to the length of the counter and maximum possible value in A. The presence of N+1 as value in A, does not cause normal incrementing. Read on!

As the count array is being developed, for the value, N + 1 = 6 in A, after N = 5, all the cell values in the count array, should be made, the highest count cell value so far. This is the real trouble in this problem: how to come up with an algorithm that will avoid running through all the count cells, making each cell value, the highest counter cell value, so far.

The solution to this problem is approached in two ways: firstly the brute force approach that runs through all the count cells, making each cell value, the highest counter cell value, so far; and secondly, a smart approach that avoids running through all the counter cells, in order to make each cell value, the highest counter cell value, so far.

Brute Force Approach

The table that shows what is happening in the brute force approach is:

There are 5 counter cells and there are 4 removable extra operations. It should have been 5 operations, but there has to be at least one operation for making the cell 1 value, the latest maximum count so far (in this case, 2). The extra 4 removable operations are to make cell 2, cell 3, cell 4, and cell 5, the latest maximum count so far (in this case, 2). Possible code for this brute force approach is:

    #include <stdio.h> 

    struct Results {
      int * C;
      int L; // Length of the array
    } stroct;

    int prevMax = 0;

    void increase(int X, int count[]) {
        count[X] += 1;
        if (count[X] > prevMax)
            prevMax = count[X];    //track previous maximum which started at 0
    }
    
    void maxCounter(int N, int prevMax, int count[]) { 
        for (int X = 1; X <= N; X++) {
            count[X] = prevMax;
        }
    }

    struct Results solution(int N, int A[], int M) {  
        int count[N+1];
        for (int i = 0; i < N+1; i++)    //including the preceding redundant (convenience) 0
            count[i] = 0;

        stroct.C = &count[0];    //stroct.C and count[] now point to the same address;  

        for (int K = 0; K < M; K++) {
            int X = A[K];
            if (1<=X && X<=N) {
                increase(X, count);
            }
            else if (X==N+1) 
                maxCounter(N, prevMax, count);
        }

        return stroct;
    }

    int main() 
    { 
        int A[] = {3, 4, 4, 6, 1, 4, 4};
        int M = sizeof(A) / sizeof(A[0]);    //divide size of array by size of one (first) element
        struct Results stru = solution(5, A, M);

        printf("%i, %i, %i, %i, %i, %i\n", stru.C[0], stru.C[1], stru.C[2], stru.C[3], stru.C[4], stru.C[5]);

        return 0; 
    } 

Note: Since the C language function cannot return an array, a struct (Results stru) with an integer sequence called C, is retuned instead.

The reader should read through the program if he/she has not already done so. The output is:

    0, 3, 2, 2, 4, 2

Unfortunately, this program has 6 counter cells, which are cell 0, cell 1, cell 2, cell 3, cell 4, and cell 5. Cell 0 should not be there, because of part of the instruction, "1 ≤ X ≤ N" where N = 5.

Well, the output of the given problem from app.codility.com/programmers is: [3, 2, 2, 4, 2]. So the candidate has to return the count array without the preceding 0.

Candidate: Always present your solution and answer, the way the examiner expects or knows.

In order to return the count array without the preceding 0, a count array of N cells, instead of N+1 has to be created; and for each of its value, 1 is subtracted from the corresponding index. That is: counter 1 becomes counter 0; counter 2 becomes counter 1; counter 3 becomes counter 2; and so on. In other words, for the example in the problem above, the 5 counters of the count array, become indexed (numbered) from index 0 to index 4, instead of from index 1 to index 5 with the preceding convenience 0. The preceding convenience 0 has to be omitted, in order to have a count array of exactly 5 cells.

The code without the C main() function, becomes:

    #include <stdio.h> 

    struct Results {
      int * C;
      int L; // Length of the array
    } stroct;

    int prevMax = 0;

    void increase(int X, int count[]) {
        count[X-1] += 1;
        if (count[X-1] > prevMax)
            prevMax = count[X-1];
    }
    
    void maxCounter(int N, int prevMax, int count[]) { 
        for (int X = 0; X < N; X++) {
            count[X] = prevMax;
        }
    }

    struct Results solution(int N, int A[], int M) {
        int count[N+1];
        for (int i = 0; i < N+1; i++)
            count[i] = 0;

        stroct.C = &count[0];    //stroct.C and count[] now point to the same address;  

        for (int K = 0; K < M; K++) {
            int X = A[K];
            if (1<=X && X<=N) {    //X cannot be 0 (given)
                increase(X, count);
            }
            else if (X==N+1) 
                maxCounter(N, prevMax, count);
        }

        return stroct;
    }

    int main() 
    { 
        int A[] = {3, 4, 4, 6, 1, 4, 4};
        int M = sizeof(A) / sizeof(A[0]);    //divide size of array by size of one (first) element
        struct Results stru = solution(5, A, M);

        printf("%i %i %i %i %i\n", stru.C[0], stru.C[1], stru.C[2], stru.C[3], stru.C[4]);

        return 0; 
    } 

The output is now,

    3 2 2 4 2

and same as from app.codility.com/programmers. The for-loop in the maxCounter() function, was also changed from "(int X = 1; X <= N; X++)" to "(int X = 0; X < N; X++)" but its body statement was not changed. In the C main() function, the expression, " <<' '<< v[5]" was removed. The reader should read the above two codes, and make the comparison, if he/she has not already done so.

There are three (non main) functions in the program. The maxCounter() function is the one that produces the removable extra operations. This function must be eliminated.

The second solution looks good, but at app.codility.com/programmers, the result for that is:

    Task score : 66% -  Correctness : 100% ; Performance : 40%
    Detected time complexity : O(MxN)

This (66%) is not good enough. What app.codility.com/programmers wants is O(N + M) time complexity. If M is 7 = 6+1 and N is 5 as above, then O(N x M) = O(7 x 5) = O(35) number of operations. What app.codility.com/programmers wants is O(N + M) = O(7 + 5) = O(12) number of operations. The number of operations to initialize all the elements of the count array, just after creation, is not included in the expected time complexity.

A normal function, solution(), in the topic of Counting Elements, should result in a time complexity of O(M + N), where M in this case is the number of elements in array, A and N is the number of cells (counters) in the count array. O(M + N) roughly means, scanning array A once in M time, and then scanning the count array, once in an additional (plus) N time.

A time complexity of O(M x N) means that, at the limit, for each value, A[K], the count array is scanned completely in N operations. In the above code, this repeated scanning is coming from the for-loop of the maxCounter() function. If the for-loop of the maxCounter() function can be reduced from xN to x1, then the time complexity of the code will go from O(N x M) to O(N + M).

What app.codility.com/programmers wants for O(M + N), is M number of operations to scan the given array, A, fitting in the appropriate "number of occurrences" as values in the count array, using the values of the given array as indexes for the count array; and additional N number of operations to "read" through the count array.

Smart Approach

For the smart approach, the table that represents the number of operations, for the above given example, is:

At the start of the principal algorithm, there is a min and max variable, each with value 0. For each "A[K] = X" for the index of array A, the counter cell, whose value is X, is incremented. If the cell value for the increment is the maximum value so far, then max becomes that value, while min remains at it previous value.

When A[K] = N + 1, and precisely A[3] = 6, max = 2, while still momentary, min = 0. Instead of making all the counter cells, 2, and wasting 4 operations, in one operation, min is then made 2 and max is made 2, saving (economizing) 4 operations.

From then onward, for any "A[K] = X" operation encountered, the counter cell, whose value is X, is incremented (by 1) and 2 is also added to the cell value. If the cell value for the increment is the maximum value so far, then max becomes that value (3 in this case), while min remains at it previous value (2 in this case). Precisely, at A[4] = 1 counter cell 1 becomes 3 and max becomes 3; counter cell 2 remains at 0, which should have been 2; counter cell 3 remains at 1, which should have been 2; counter cell 4 remains at 2, and that is alright because it was the previous max; and counter cell 5 remains at 0, which should have been 2.

At A[5] = 4 counter cell 1 remains at 3, and it is above 2; counter cell 2 remains at 0, which should have been 2, counter cell 3 remains at 1, which should have been 2, counter cell 4 increments to 3, but max remains at 3 from previous operation; and counter cell 5 remains at 0, which should have been 2 (the latest min).

At A[6] = 4 counter cell 1 remains at 3, and it is above 2; counter cell 2 remains at 0, which should have been 2, counter cell 3 remains at 1, which should have been 2, counter cell 4 increments to 4, and the new max becomes 4; and counter cell 5 remains at 0, which should have been 2 (the latest min).

The length of array A ends at index 6. So the output has to be made. The last line of the above table at index 6 cannot be returned, because some values that are supposed to be at the new min, 2, are still below 2.

An extra N operations have to be made, to make all the counter cells, whose values are less than 2, to be 2. If that is done, the output will be:

    0 3 2 2 4 2

Again, the issue of the unwanted preceding 0! To solve this problem, assign the cell value of counter index 1 to index 0, counter index 2 to index 1, index 3 to index 2, index 4 to index 3, and index 5 to index 4. The following table illustrates this (at the first full row):

The return array (output) is now correct, as:

    3 2 2 4 2

Generally, each time "A[K] = N + 1" is encountered, for the index of array A, the value of min becomes the highest value so far, and the value of max also becomes the same highest value so far. There after, the value of max continues to increase with each operation, until "A[K] = N + 1" is encountered again. There is only one case for "A[K] = N + 1" above, with max = 2 = min. There can be more than one case. There can be more than one case, with for example, max = 7 = min, max = 10 = min, max = 14 = min, and so on.

And the ultimate code is:

    #include <stdio.h> 

    struct Results {
      int * C;
      int L; // Length of the array
    } stroct;

    struct Results solution(int N, int A[], int M) {
        int count[N+1];
        for (int i = 0; i < N+1; i++)
            count[i] = 0;

        stroct.C = &count[0];    //stroct.C and count[] now point to the same address;  

        int min = 0; 
        int max = 0; 

        for (int K = 0; K < M; K++) {
            if (A[K]>=1 && A[K]<=N) {    //given
                if(count[A[K]-1] < min)
                    count[A[K]-1] = min+1;    //for vertically trailing counter after max memorized
                else
                    count[A[K]-1]++;    //for counter with last maximum value
                
                if(count[A[K]-1] > max)
                    max = count[A[K]-1];    //memorize latest maximum value for all future counters
            }
            else if (A[K]==N+1) 
                min = max;    //memorize latest minimum, which is same as latest maximum
        }

        for (int X = 0; X < N; X++) {  
            if (count[X] < min)    //if any counter value is less than latest minimum before read-out, after last maximum effect of A[K] = N + 1,
                count[X] = min;    //no counter cell should be less than latest minimum
        }

        return stroct;
    }

    int main() 
    { 
        int A[] = {3, 4, 4, 6, 1, 4, 4};
        int M = sizeof(A) / sizeof(A[0]);    //divide size of array by size of one (first) element
        struct Results stru = solution(5, A, M);

        printf("%i %i %i %i %i\n", stru.C[0], stru.C[1], stru.C[2], stru.C[3], stru.C[4]);

        return 0; 
    } 

The result from app.codility.com/programmers for this solution() function is:

    Task score : 100% -  Correctness : 100% ; Performance : 100%
    Detected time complexity : O(N+M)

Conclusion

The reader must read this conclusion: With the smart (last) solution, when a counter is addressed based on a value in array A, the counter is normally incremented by 1. However, when the value of N+1 is reached in A, the maximum value among all the counters is remembered. This maximum value is also the new minimum value moving forward. When any counter is to be addressed again, if its value is less than this minimum value, the value is made this minimum value, and at the same time incremented by 1 (i.e. min+1). If the counter is the one with the maximum value, its value is simply increased by 1. The incrementation of any counter addressed, continues until a value of N+1 is reached again in A; and the "cycle" repeats from there. All that is done in one for-loop.

The outputs from all the counters are required, just after the end of the array A is reached. When that point is reached, a second and last for-loop in the solution() function, goes through the count array, and if the value of any counter is below the latest minimum value, it makes it that minimum value. The reader should remember that when the value of N+1 is reached in A, all counters are supposed to be made the maximum value (which is the new minimum value).

The reader should read through the last code presented above again, in order to appreciate this conclusion.

The reader should register at app.codility.com/programmers, so that he/she should be testing his/her code.