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:
def 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 write to stdout for debugging purposes, e.g.
# print "this is a debug message"
def solution(N, A):
# write your code in Python 2.7
rmin = 0
rmax = 0
C = [0] * N
M = len(A)
if not M:
return C
for i in range(M):
X = A[i]
if X <= N:
X = X - 1
c = C[X]
if c < rmin:
c = rmin + 1
else:
c = c + 1
rmax = max(rmax, c)
C[X] = c
elif X == N+1:
rmin = rmax
print C
for i in range(N):
if C[i] < rmin:
C[i] = rmin
return C
[5, []]
[6, [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]]
[10, [11, 11, 11, 11]]
function result: [0, 0, 0, 0, 0]
function result: [17, 0, 0, 0, 0, 0]
[17, 0, 0, 0, 0, 0]
function result: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
# you can write to stdout for debugging purposes, e.g.
# print "this is a debug message"
def solution(N, A):
# write your code in Python 2.7
rmin = 0
rmax = 0
C = [0] * N
M = len(A)
if not M:
return C
for i in range(M):
X = A[i]
if X <= N:
X = X - 1
c = C[X]
if c < rmin:
c = rmin + 1
else:
c = c + 1
rmax = max(rmax, c)
C[X] = c
elif X == N+1:
rmin = rmax
for i in range(N):
if C[i] < rmin:
C[i] = rmin
return C
[5, []]
[6, [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]]
[10, [11, 11, 11, 11]]
function result: [0, 0, 0, 0, 0]
function result: [17, 0, 0, 0, 0, 0]
function result: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
# you can write to stdout for debugging purposes, e.g.
# print "this is a debug message"
def solution(N, A):
# write your code in Python 2.7
rmin = 0
rmax = 0
C = [0] * N
M = len(A)
if not M:
return C
for i in range(M):
X = A[i]
if X <= N:
X = X - 1
c = C[X]
if c < rmin:
c = rmin + 1
else:
c = c + 1
rmax = max(rmax, c)
C[X] = c
elif X == N+1:
rmin = rmax
for i in range(N):
if C[i] < rmin:
C[i] = rmin
return C
[5, []]
[6, [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]]
[10, [11, 11, 11, 11]]
function result: [0, 0, 0, 0, 0]
function result: [17, 0, 0, 0, 0, 0]
function result: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
# you can write to stdout for debugging purposes, e.g.
# print "this is a debug message"
def solution(N, A):
# write your code in Python 2.7
rmin = 0
rmax = 0
C = [0] * N
M = len(A)
if not M:
return C
for i in range(M):
X = A[i]
if X <= N:
X = X - 1
c = C[X]
if c < rmin:
c = rmin + 1
else:
c = c + 1
rmax = max(rmax, c)
C[X] = c
elif X == N+1:
rmin = rmax
for i in range(N):
if C[i] < rmin:
C[i] = rmin
return C
The solution obtained perfect score.