MaxCounters

Task

This task is a functional operation task, involving commands that can operate on all items in an array:

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:vector<int> solution(int N, vector<int> &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].

Solution

The main thing is to avoid operations on all items in the array. Instead you keep a track of the maximum value in the array, as well as the maximum value the last time a ‘max counter’ command was received. Then the result array is adjusted before returning it.

This solution is O(N+M).


#include <iostream>
using namespace std;
#include <cassert>
#include <vector>

vector<int> solution(int N, vector<int> &A) {
  // write your code in C++14 (g++ 6.2.0)
  vector<int> res(N);
  int lastMaxSet = -1, maxVal = 0;
  for (size_t i = 0; i < A.size(); i++) {

    int cmd = A[i];
    assert(cmd <= N + 1);
    assert(cmd >= 1);
    if (cmd == N + 1) {
      // set all to max
      lastMaxSet = maxVal;

    } else {
      int curVal = res[cmd – 1];
      // any items < last max have not been set to max yet
      if (curVal < lastMaxSet) {
        curVal = lastMaxSet;
      }
      curVal++;
      res[cmd – 1] = curVal;
      maxVal = max(curVal, maxVal);
    }
  } // for each cmd
  // now update with any pending max
  for (size_t i = 0; i < N; i++) {
    int curVal = res[i];
    if (curVal < lastMaxSet) {
      res[i] = lastMaxSet;
    }
  } // for each in result
  return res;
}

Test Function

This code tests the solution


int main() {
  vector<int> v1{3, 4, 4, 6, 1, 4, 4};
  vector<int> exp1{3, 2, 2, 4, 2};
  vector<int> res = solution(5, v1);
  assert(res.size() == exp1.size());
  for (size_t i = 0; i < exp1.size(); i++) {
    assert(res[i] == exp1[i]);
  }

  vector<int> v2{3, 4, 4, 100001, 1, 4, 4};
  vector<int> exp2{3, 2, 2, 4, 2,2,2,2,2,2,2};
  res = solution(100000, v2);

  for (size_t i = 0; i < exp1.size(); i++) {
    assert(res[i] == exp2[i]);
  }

  return 0;
}

Results

Correctness	100%
Performance	100%
Time Complexity	O(N+M)

MaxCounters

Task

Solution

Test Function

Results

Index of solutions to Codility Lessons

Leave a Reply Cancel reply