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:
function 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] = 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].
// you can use print for debugging purposes, e.g.
// print "this is a debug message\n";
function solution($N, $A) {
$max =0;
$maxIdx = 0;
$maxVal = 0;
$result = array_fill(0,$N, 0);
foreach($A as $key => $inc) {
if($inc < $N+1) {
$result[$inc-1]++;
if($max < $result[$inc-1]) {
$max = $result[$inc-1];
}
} else if($inc == $N+1) {
$maxVal = $max;
$maxIdx = $key;
}
}
$result = array_fill(0,$N, $maxVal);
for ($i=$maxIdx; $i < count($A); $i++) {
if($A[$i] < $N+1) {
$result[$A[$i]-1]++;
}
}
return $result;
}
// you can use print for debugging purposes, e.g.
// print "this is a debug message\n";
function solution($N, $A) {
$max =0;
$maxIdx = 0;
$maxVal = 0;
$result = array_fill(0,$N, 0);
foreach($A as $key => $inc) {
if($inc < $N+1) {
$result[$inc-1]++;
if($max < $result[$inc-1]) {
$max = $result[$inc-1];
}
} else if($inc == $N+1) {
$maxVal = $max;
$maxIdx = $key;
}
}
$result = array_fill(0,$N, $maxVal);
for ($i=$maxIdx; $i < count($A); $i++) {
if($A[$i] < $N+1) {
$result[$A[$i]-1]++;
}
}
return $result;
}
[10000, [3, 4, 4, 6, 10000, 4, 4]]
function result: [0, 0, 1, 4, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0...
// you can use print for debugging purposes, e.g.
// print "this is a debug message\n";
function solution($N, $A) {
$max =0;
$maxIdx = 0;
$maxVal = 0;
$result = array_fill(0,$N, 0);
foreach($A as $key => $inc) {
if($inc < $N+1) {
$result[$inc-1]++;
if($max < $result[$inc-1]) {
$max = $result[$inc-1];
}
} else if($inc == $N+1) {
$maxVal = $max;
$maxIdx = $key;
}
}
$result = array_fill(0,$N, $maxVal);
for ($i=$maxIdx; $i < count($A); $i++) {
if($A[$i] < $N+1) {
$result[$A[$i]-1]++;
}
}
return $result;
}
[10000, [3, 4, 4, 6, 10001, 4, 4]]
function result: [2, 2, 2, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2...
// you can use print for debugging purposes, e.g.
// print "this is a debug message\n";
function solution($N, $A) {
$max =0;
$maxIdx = 0;
$maxVal = 0;
$result = array_fill(0,$N, 0);
foreach($A as $key => $inc) {
if($inc < $N+1) {
$result[$inc-1]++;
if($max < $result[$inc-1]) {
$max = $result[$inc-1];
}
} else if($inc == $N+1) {
$maxVal = $max;
$maxIdx = $key;
}
}
$result = array_fill(0,$N, $maxVal);
for ($i=$maxIdx; $i < count($A); $i++) {
if($A[$i] < $N+1) {
$result[$A[$i]-1]++;
}
}
return $result;
}
// you can use print for debugging purposes, e.g.
// print "this is a debug message\n";
function solution($N, $A) {
$max =0;
$maxIdx = 0;
$maxVal = 0;
$result = array_fill(0,$N, 0);
foreach($A as $key => $inc) {
if($inc < $N+1) {
$result[$inc-1]++;
if($max < $result[$inc-1]) {
$max = $result[$inc-1];
}
} else if($inc == $N+1) {
$maxVal = $max;
$maxIdx = $key;
}
}
$result = array_fill(0,$N, $maxVal);
for ($i=$maxIdx; $i < count($A); $i++) {
if($A[$i] < $N+1) {
$result[$A[$i]-1]++;
}
}
return $result;
}
// you can use print for debugging purposes, e.g.
// print "this is a debug message\n";
function solution($N, $A) {
$max =0;
$maxIdx = 0;
$maxVal = 0;
$result = array_fill(0,$N, 0);
foreach($A as $key => $inc) {
if($inc < $N+1) {
$result[$inc-1]++;
if($max < $result[$inc-1]) {
$max = $result[$inc-1];
}
} else if($inc == $N+1) {
$maxVal = $max;
$maxIdx = $key;
}
}
$result = array_fill(0,$N, $maxVal);
for ($i=$maxIdx; $i < count($A); $i++) {
if($A[$i] < $N+1) {
$result[$A[$i]-1]++;
}
}
return $result;
}
// you can use print for debugging purposes, e.g.
// print "this is a debug message\n";
function solution($N, $A) {
$max =0;
$maxIdx = 0;
$maxVal = 0;
$result = array_fill(0,$N, 0);
foreach($A as $key => $inc) {
if($inc < $N+1) {
$result[$inc-1]++;
if($max < $result[$inc-1]) {
$max = $result[$inc-1];
}
} else if($inc == $N+1) {
$maxVal = $max;
$maxIdx = $key;
}
}
$result = array_fill(0,$N, $maxVal);
for ($i=$maxIdx; $i < count($A); $i++) {
if($A[$i] < $N+1) {
$result[$A[$i]-1]++;
}
}
return $result;
}
The following issues have been detected: wrong answers.
small random test, 6 max_counter operations
got [4, 4, 4, 4, 4, 4, 4,.. expected [9, 9, 9, 9, 9, 9, 9,..
small random test, 10 max_counter operations
got [4, 4, 4, 4, 4, 4, 4,.. expected [10, 10, 10, 10, 10, ..
medium random test, 50 max_counter operations
got [5, 5, 5, 5, 5, 5, 5, .. expected [53, 53, 53, 53, 53, 5..
medium random test, 500 max_counter operations
got [7, 7, 7, 7, 7, 7, 7,.. expected [325, 325, 325, 325, ..
large random test, 2120 max_counter operations
got [7, 7, 7, 7, 7, 7, 7,.. expected [1968, 1968, 1968, 19..
large random test, 10000 max_counter operations
got [11, 11, 11, 11, 11, .. expected [9002, 9002, 9002, 90..