StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POAlgorithm: Max Counters
text
Body
copied!<p>I have the following problem:</p> <p>You are given N counters, initially set to 0, and you have two possible operations on them:</p> <ul> <li>increase(X) − counter X is increased by 1, </li> <li>max_counter − all counters are set to the maximum value of any counter.</li> </ul> <p>A non-empty zero-indexed array A of M integers is given. This array represents consecutive operations:</p> <ul> <li>if A[K] = X, such that 1 ≤ X ≤ N, then operation K is increase(X),</li> <li>if A[K] = N + 1 then operation K is max_counter.</li> </ul> <p>For example, given integer N = 5 and array A such that:</p> <pre><code>A[0] = 3 A[1] = 4 A[2] = 4 A[3] = 6 A[4] = 1 A[5] = 4 A[6] = 4 </code></pre> <p>the values of the counters after each consecutive operation will be:</p> <pre><code>(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) </code></pre> <p>The goal is to calculate the value of every counter after all operations.</p> <p>I did the following solution but it runs at O(NK) where K = length of array A.</p> <pre><code>public int[] solution(int N, int[] A) { int[] result = new int[N]; int maximum = 0; for (int K = 0; K < A.Length; K++) { if (A[K] < 1 || A[K] > N + 1) throw new InvalidOperationException(); if (A[K] >= 1 && A[K] <= N) { result[A[K] - 1]++; if (result[A[K] - 1] > maximum) { maximum = result[A[K] - 1]; } } else { // inefficiency here for (int i = 0; i < result.Length; i++) result[i] = maximum; } } return result; } </code></pre> <p>Could anyone show me how this can be better done with O(N + K) where K is the length of array A? Sorry for may terrible coding, I am doing these exercises to improve my programming. Thanks!</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload