MaxCounters at app.codility.com-programmers in C Plus Plus Explained
Calculate the values of counters after applying all alternating operations - increase counter by 1, set value of all counters to current maximum
Foreword: Category of Article - Technology, Computers and Software, Algorithm
By: Chrysanthus Date Published: 26 Jan 2024
Task
Detected time complexity : O(M+N)
Lesson 4 at app.codility.com/programmers
The solution and its explanation are given below.
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 vector A of M integers is given. This vector 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 vector 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 vector A consisting of M integers, returns a sequence of integers representing the values of the counters.
Result vector should be returned as a vector 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 vector A is an integer within the range [1..N + 1].
Note:
There is a count vector, where each element counts some form of number of occurrences, in some M operations, associated with some logic. The example above has N = 5 and M = 7. In the following table, there are M rows for the M operations and associated logic. There are 6 columns, including an extra first column for index 0 at the count vector. This extra preceding column is for the convenience zero. It is not used in the first solution below.
| Index | Operations | 0 | 1 | 2 | 3 | 4 | 5 |
| 0 | 0 | 0 | 0 | 0 | 0 | ||
| M | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 | 1 | 1 | 0 | |
| 2 | 0 | 0 | 0 | 1 | 2 | 0 | |
| 3 | 0 | 2 | 2 | 2 | 2 | 2 | |
| 4 | 0 | 3 | 2 | 2 | 2 | 2 | |
| 5 | 0 | 3 | 2 | 2 | 3 | 2 | |
| 6 | 0 | 3 | 2 | 2 | 4 | 2 |
With zero based row counting, the rows are numbered from 0 to 6 = 7 - 1.
By the two possible operations, when M = 0, A[0] = 3, and since 1<=3<=5, the element in the count vector at index 3, is increased by 1, and the rest of the elements remain at their previous values.
When M = 1, A[1] = 4, and since 1<=4<=5, the element in the count vector at index 4, is increased by 1, and the rest of the elements remain at their previous values.
When M = 2, A[2] = 4, and since 1<=4<=5, the element in the count vector at index 4, is increased by 1 to become 2, and the rest of the elements remain at their previous values.
When M = 3, A[3] = 6. This time, 6 is not in the inclusive range from 1 to 5. And 6 = N+1 = 5+1. So, all the elements in the count vector, from index 1 to 5, become the highest value for any of the indexes. They all become 2.
When M = 4, A[4] = 1, and since 1<=1<=5, the element in the count vector at index 1, is increased by 1, from 2 to 3, and the rest of the elements remain at their previous value of 2.
When M = 5, A[5] = 4, and since 1<=4<=5, the element in the count vector at index 4, is increased by 1, from 2 to 3, and the rest of the elements remain at their previous values.
When M = 5, A[5] = 4, and since 1<=4<=5, the element in the count vector at index 4, is increased by 1, from 3 to 4, and the rest of the elements remain at their previous values.
Obvious Resulting Function with count Vector
The two possible operations,
- "increase(X) - counter X is increased by 1,"
- "max counter - all counters are set to the maximum value of any counter."
can be seen as functions. X is an index of the count vector. K is an index of the given vector, A of M integers. N is the number of cells in the count vector with "multiple occurrence" values (integers).
increase(X) increases the value of the counter at index, X even if the value was the previous highest value.
The obvious code will scan the count vector, setting all its elements to the current highest value, when A[K] = N + 1. The obvious program is:
#include <iostream>
#include <vector>
using namespace std;
int prevMax = 0;
void increase(int X, vector<int> &count) {
count[X] += 1;
if (count[X] > prevMax)
prevMax = count[X];
}
void maxCounter(int N, int prevMax, vector<int> &count) {
for (int X = 1; X <= N; X++) {
count[X] = prevMax; //track previous maximum which started at 0
}
}
vector<int> solution(int N, vector<int> &A) {
vector<int> count(N+1, 0); //including the preceding redundant (convenience) 0
int M = A.size();
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 count;
}
int main()
{
vector<int> A{3, 4, 4, 6, 1, 4, 4};
vector<int> v = solution(5, A);
cout << v[0] <<' '<< v[1] <<' '<< v[2] <<' '<< v[3] <<' '<< v[4] <<' '<< v[5] << endl;
return 0;
}
The reader should read through the program if he/she has not already done so. The output is:
0 3 2 2 4 2
However, 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 vector without the preceding 0.
Candidate: Always present your solution and answer, the way the examiner expects or knows.
In order to return the count vector without the preceding 0, a count vector 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 vector, 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 vector of exactly 5 cells. The code without the C++ main() function, becomes:
#include <iostream>
#include <vector>
using namespace std;
int prevMax = 0;
void increase(int X, vector<int> &count) {
count[X-1] += 1;
if (count[X-1] > prevMax)
prevMax = count[X-1];
}
void maxCounter(int N, int prevMax, vector<int> &count) {
for (int X = 0; X < N; X++) {
count[X] = prevMax;
}
}
vector<int> solution(int N, vector<int> &A) {
vector<int> count(N, 0);
int M = A.size();
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 count;
}
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++)" and 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.
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 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 vector, just after creation, is not included in the 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 vector, A and N is the number of cells (counters) in the count vector. O(M + N) roughly means, scanning vector A once in M time, and then scanning the count vector, 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 vector 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 vector, A, fitting in the appropriate "number of occurrences" as values in the count vector, using the values of the given vector as indexes for the count vector; and additional N number of operations to "read" through the count vector. What app.codility.com/programmers wants is a program like this:
#include <iostream>
#include <vector>
using namespace std;
vector<int> solution(int N, vector<int> &A) {
vector<int> count(N, 0);
int min = 0;
int max = 0;
int M = A.size();
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 trailing counter
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 the 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 should be less than latest minimum
}
return count;
}
int main()
{
vector<int> A{3, 4, 4, 6, 1, 4, 4};
vector<int> v = solution(5, A);
cout << v[0] <<' '<< v[1] <<' '<< v[2] <<' '<< v[3] <<' '<< v[4] << endl;
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)
In a basic Counting Elements (topic) solution(), an increase by 1 in a counter, is an increase (repetition) by 1, in the number of occurrences of the index of that counter (in the count vector), as value in the given vector, A. In the problem given, while vector A is being scanned, when A[K] = N+1, all the counters take the value of the current maximum counter value (which can also be seen as the previous maximum count value, while scanning the given vector, A from left to right (top to bottom)). As the two main possible operations are executed, according to the values of the A vector, some counters trail behind, the latest minimum value, which is the last maximum value of one of the counters.
In the first for-loop in the solution() function here, after each of the seven iterations (based on the example of the problem), the content of the count vector of five counters (left), is put along side the expected output content of the five counters (table above), as follows:
| Count Vector just after First for-Loop | Count Vector expected Outputs (from above) | |||||||||||
| Index | Operations | 0 | 1 | 2 | 3 | 4 | 0 | 1 | 2 | 3 | 4 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |||
| M | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | |
| 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | ||
| 2 | 0 | 0 | 1 | 2 | 0 | 0 | 0 | 1 | 2 | 0 | ||
| 3 | 0 | 0 | 1 | 2 | 0 | 2 | 2 | 2 | 2 | 2 | ||
| 4 | 3 | 0 | 1 | 2 | 0 | 3 | 2 | 2 | 2 | 2 | ||
| 5 | 3 | 0 | 1 | 3 | 0 | 3 | 2 | 2 | 3 | 2 | ||
| 6 | 3 | 0 | 1 | 4 | 0 | 3 | 2 | 2 | 4 | 2 | ||
The reader should read through the above solution() function and its comments, if he/she has not already done so. The reader should be comparing the two sub-tables here, as he/she reads the following text:
In this new solution() function, the first for-loop addresses only one counter (among the N counters), for each value, A[K]. Only one counter is addressed at a time for each A[K]. There are five different possible values (integers) for each A[K], corresponding to the five different counters in the count vector. The counter addressed (based on its index), depends on the value (integer) of A[K].
When A[K] is an integer between 1 and N inclusive, the value (count[A[K]-1]) for that particular counter, is increased by 1.
When A[K] = N + 1, where N is the number of counters, it is the counter with the previous maximum value that is addressed. Addressing this counter just maintains the value at the previous maximum value.
When A[K] = N + 1, this solution() function does not waste operations in an extra for-loop, to put all the counters at the current maximum value, which is the value of one of the counters (not the same counter all the time), that is highest among all the counters at that time. The solution() function however, memorizes the last maximum value in the variable, max.
Since this solution() does not make all the counters, the current maximum value, some counters trail behind as incrementation continues. Since some counters trail behind the minimum value, the last for-loop in the solution() function, not present in the previous two programs, bring up any counter that was trailing, to the minimum value, which was the last maximum value, which was supposed to have been distributed to the rest of the counters.
In the scanning of the given vector, A, the omission of the extra for-loop to address all the counters, putting them at the current maximum value, when A[K] = N + 1, in the maxCounter() function, is what brings out the advantage (reduced number of operations) of this solution() function, over the previous two programs.
At this point, the reader should re-read over the above final program of O(M+N) time complexity, and its comments. Remember that the tests at app.codility.com/programmers do not accept the C++ main() function from the candidate.
The solution() function without the comments is re-typed below for easy reference by the reader:
#include <iostream>
#include <vector>
using namespace std;
vector<int> solution(int N, vector<int> &A) {
vector<int> count(N, 0);
int min = 0;
int max = 0;
int M = A.size();
for (int K = 0; K < M; K++) {
if (A[K]>=1 && A[K]<=N) {
if(count[A[K]-1] < min)
count[A[K]-1] = min+1;
else
count[A[K]-1]++;
if(count[A[K]-1] > max)
max = count[A[K]-1];
}
else if (A[K]==N+1)
min = max;
}
for (int X = 0; X < N; X++) {
if (count[X] < min)
count[X] = min;
}
return count;
}
The main for-loop here scans the given vector. And so some counters may only be addressed at the end, by the second for-loop. Before this solution() function is called, each counter is a minimum value as well as is a maximum value. The minimum value among all the counters addressed so far, is always remembered against the next element of vector A, by the min variable, initialized to 0 at the start. The maximum value among all the counters addressed so far, is always remembered against the next element of vector A, by the max variable, initialized to 0 at the start.
Conclusion
The outputs from all the counters are required, just after the end of the vector A is reached. When that point is reached, a second and last for-loop in the solution() function, goes through the count vector, 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), while the counter with the maximum value remains at the new maximum.
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.