Solution to Max-Counters by codility | Code Says

Solution to Max-Counters by codility | Code Says

Lesson 2 - Counting Elements: 

Question: http://codility.com/demo/take-sample-test/max_counters

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 zero-indexed 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.

http://www.martinkysel.com/codility-maxcounters-solution/

The idea is to perform the specified operation as stated. It is not required to iterate over the whole array if a new value is set for all the values. Just save the value and check it when an increase on that position is performed.

vector<int> solution(int N, vector<int> &A) {

    vector<int> sol;

    int current_max = 0;

    int last_increase = 0;

 

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

        sol.push_back(0);

    }

 

    for(unsigned int i=0; i<A.size();i++){

        if (A[i] > N) {

            last_increase = current_max;

        } else {

            sol[A[i]-1] = max(sol[A[i]-1], last_increase);

            sol[A[i]-1]++;

            current_max = max(current_max, sol[A[i]-1]);

        }

    }

 

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

        sol[i] = max(sol[i], last_increase);

    }

 

    return sol;

}

We could use lazy-write to improve the performance. When receiving the max_counter command, we record the current-max value, but do not change the list content. Only when we are going to return the list or increace a specific element, we will apply the stored value to the corresponding element(s).

def solution(N, A):

    result = [0]*N    # The list to be returned

    max_counter = 0   # The used value in previous max_counter command

    current_max = 0   # The current maximum value of any counter

 

    for command in A:

        if 1 <= command <= N:

            # increase(X) command

            if max_counter > result[command-1]:

                # lazy write

                result[command-1] = max_counter

            result[command-1] += 1

            if current_max < result[command-1]:

                current_max = result[command-1]

        else:

            # max_counter command

            # just record the current maximum value for later write

            max_counter = current_max

 

    for index in range(0,N):

        if result[index] < max_counter:

            # This element has never been used/updated after previous

            #     max_counter command

            result[index] = max_counter

 

    return result

A straightforward solution is easy as following. But the expected worst-case time complexity cannot be guaranteed.

ad solution to Max-Counters by codility

Python

1 2 3 4 5 6 7 8 9 10

def solution(N, A):     result = [0]*N       for command in A:         if 1 <= command <= N:             result[command-1] += 1         else:             result[:] = [max(result)]*N       return result

http://codility-lessons.blogspot.com/2014/07/lesson-2maxcounters.html
http://jimii.github.io/blog/2014/09/19/codility-counting-elements-maxcounters/
Read full article from Solution to Max-Counters by codility | Code Says