Tasks Details
medium
1.
MaxCounters
Calculate the values of counters after applying all alternating operations: increase counter by 1; set value of all counters to current maximum.
Task Score
77%
Correctness
100%
Performance
60%
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] = 4the 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:
class Solution { public int[] solution(int N, 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] = 4the 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–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used C#
Time spent on task 88 minutes
Notes
not defined yet
Task timeline
Code: 00:05:23 UTC,
cs,
verify,
result: Failed
using System;
// you can also use other imports, for example:
// using System.Collections.Generic;
// you can write to stdout for debugging purposes, e.g.
// Console.WriteLine("this is a debug message");
class Solution {
public int[] ssolution(int N, int[] A) {
// write your code in C# 6.0 with .NET 4.5 (Mono)
}
}
Analysis
Compile error
Compilation failed: 2 error(s), 0 warnings user.cs(30,22): error CS1061: Type `Solution' does not contain a definition for `solution' and no extension method `solution' of type `Solution' could be found. Are you missing an assembly reference? Solution.cs(8,7): (Location of the symbol related to previous error) Solution.cs(9,18): error CS0161: `Solution.ssolution(int, int[])': not all code paths return a value
Code: 00:05:43 UTC,
cs,
verify,
result: Failed
using System;
// you can also use other imports, for example:
// using System.Collections.Generic;
// you can write to stdout for debugging purposes, e.g.
// Console.WriteLine("this is a debug message");
class Solution {
public int[] solution(int N, int[] A) {
// write your code in C# 6.0 with .NET 4.5 (Mono)
}
}
Analysis
Compile error
Compilation failed: 1 error(s), 0 warnings Solution.cs(9,18): error CS0161: `Solution.solution(int, int[])': not all code paths return a value
Code: 01:30:25 UTC,
cs,
verify,
result: Passed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859
using System;
class Solution {
public class Counters
{
private int[] counters;
private int greaterValueInCounter = 0;
public Counters(int length)
{
counters = new int[length];
}
public void MaxAllCounters()
{
for (int i = 0; i < counters.Length; i++)
{
counters[i] = greaterValueInCounter;
}
}
public void IncreaseCounter(int counterPosition)
{
//The counter is one-based, but our array is zero-based
counterPosition--;
//Increments the counter
counters[counterPosition]++;
if (counters[counterPosition] > greaterValueInCounter)
greaterValueInCounter = counters[counterPosition];
}
//Law of Demter! The counters array is encapsuled in this class so if we provide
//external acess to it anyone could modify it and break the purpose of the encapsulations
//So we just exposes a copy of it :)
public int[] ToArray()
{
return (int[])counters.Clone();
}
}
//I didn't refactored the names of the variables N and A
//to maintain it aligned with the question description
public int[] solution(int N, int[] A)
{
var counters = new Counters(N);
for (int k = 0; k < A.Length; k++)
{
if (A[k] <= N)
counters.IncreaseCounter(A[k]);
else
counters.MaxAllCounters();
}
return counters.ToArray();
}
}
Analysis
Code: 01:31:15 UTC,
cs,
verify,
result: Passed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960
using System;
class Solution {
//I didn't refactored the names of the variables N and A
//to maintain it aligned with the question description
public int[] solution(int N, int[] A)
{
var counters = new Counters(N);
for (int k = 0; k < A.Length; k++)
{
if (A[k] <= N)
counters.IncreaseCounter(A[k]);
else
counters.MaxAllCounters();
}
return counters.ToArray();
}
public class Counters
{
private int[] counters;
private int greaterValueInCounter = 0;
public Counters(int length)
{
counters = new int[length];
}
public void MaxAllCounters()
{
for (int i = 0; i < counters.Length; i++)
{
counters[i] = greaterValueInCounter;
}
}
public void IncreaseCounter(int counterPosition)
{
//The counter is one-based, but our array is zero-based
counterPosition--;
//Increments the counter
counters[counterPosition]++;
if (counters[counterPosition] > greaterValueInCounter)
greaterValueInCounter = counters[counterPosition];
}
//Law of Demter! The counters array is encapsuled in this class so if we provide
//external acess to it anyone could modify it and break the purpose of the encapsulations
//So we just exposes a copy of it :)
public int[] ToArray()
{
return (int[])counters.Clone();
}
}
}
Analysis
Code: 01:32:16 UTC,
cs,
verify,
result: Passed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960
using System;
class Solution {
//I didn't refactored the names of the variables N and A
//to maintain it aligned with the question description
public int[] solution(int N, int[] A)
{
var counters = new Counters(N);
for (int k = 0; k < A.Length; k++)
{
if (A[k] <= N)
counters.IncreaseCounter(A[k]);
else
counters.MaxAllCounters();
}
return counters.ToArray();
}
public class Counters
{
private int[] counters;
private int greaterValueInCounter = 0;
public Counters(int length)
{
counters = new int[length];
}
public void MaxAllCounters()
{
for (int i = 0; i < counters.Length; i++)
{
counters[i] = greaterValueInCounter;
}
}
public void IncreaseCounter(int counterPosition)
{
//The counter is one-based, but our array is zero-based
counterPosition--;
//Increments the counter
counters[counterPosition]++;
if (counters[counterPosition] > greaterValueInCounter)
greaterValueInCounter = counters[counterPosition];
}
//Law of Demter! The counters array is encapsuled in this class so if we provide
//external acess to it anyone could modify it and break the purpose of the encapsulations
//So we just exposes a copy of it :)
public int[] ToArray()
{
return (int[])counters.Clone();
}
}
}
Analysis
Code: 01:32:19 UTC,
cs,
final,
score:
77
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960
using System;
class Solution {
//I didn't refactored the names of the variables N and A
//to maintain it aligned with the question description
public int[] solution(int N, int[] A)
{
var counters = new Counters(N);
for (int k = 0; k < A.Length; k++)
{
if (A[k] <= N)
counters.IncreaseCounter(A[k]);
else
counters.MaxAllCounters();
}
return counters.ToArray();
}
public class Counters
{
private int[] counters;
private int greaterValueInCounter = 0;
public Counters(int length)
{
counters = new int[length];
}
public void MaxAllCounters()
{
for (int i = 0; i < counters.Length; i++)
{
counters[i] = greaterValueInCounter;
}
}
public void IncreaseCounter(int counterPosition)
{
//The counter is one-based, but our array is zero-based
counterPosition--;
//Increments the counter
counters[counterPosition]++;
if (counters[counterPosition] > greaterValueInCounter)
greaterValueInCounter = counters[counterPosition];
}
//Law of Demter! The counters array is encapsuled in this class so if we provide
//external acess to it anyone could modify it and break the purpose of the encapsulations
//So we just exposes a copy of it :)
public int[] ToArray()
{
return (int[])counters.Clone();
}
}
}Analysis summary
The following issues have been detected: timeout errors.
Analysis
Detected time complexity:
O(N*M)
expand all
Performance tests
1.
0.056 s
OK
1.
0.062 s
OK
1.
0.146 s
OK
large_random2
large random test, 10000 max_counter operations
large random test, 10000 max_counter operations
✘
TIMEOUT ERROR
running time: 0.46 sec., time limit: 0.42 sec.
running time: 0.46 sec., time limit: 0.42 sec.
1.
0.464 s
TIMEOUT ERROR,
running time: 0.46 sec., time limit: 0.42 sec.
extreme_large
all max_counter operations
all max_counter operations
✘
TIMEOUT ERROR
running time: >6.00 sec., time limit: 0.46 sec.
running time: >6.00 sec., time limit: 0.46 sec.
1.
6.000 s
TIMEOUT ERROR,
running time: >6.00 sec., time limit: 0.46 sec.
2.
0.097 s
OK