[Codility] Lesson-04.2: MaxCounters

The problem named ‘MaxCounters’ is handled via this post. The URL for confirming the original task is the following.

MaxCounters coding task - Learn to Code - Codility

Task Description

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.

Write a function:

def solution(N, A)

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 an array of integers.

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].

Copyright 2009–2020 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

Key Point

• Writing an efficient solution has become a fundamental manner.
• For avoiding the nested loop operation, initialize the variables, and use them for helping calculation. The solution, provided in this post, uses two extra variables named with ‘max_val’ and ‘tmp_max’ are used.

Solution (using Python)

def solution(N, A):
    array, max_val, tmp_max = [0] * N, 0, 0
    for elm in A:
        if(elm > N): max_val = tmp_max
        else:
            if(array[elm-1] < max_val): array[elm-1] = max_val + 1
            else: array[elm-1] += 1
            tmp_max = max(tmp_max, array[elm-1])
    for idx in range(N):
        if(array[idx-1] < max_val): array[idx-1] = max_val
return array

Please use the above solution for reference.
I recommend you to write your own source code.

Related Post

[Codility] Lesson-04.1: FrogRiverOne

[Codility] Lesson-04.3: MissingInteger