2

I am trying to solve this problem on HackerRank:

Animesh has N empty candy jars numbered from 1 to N with infinite capacity. He performs M operations. Each operation is described by 3 integers a, b and k where a and b are index of >the jars and k is the number of candies to be added inside each jar with index between a and >b (both inclusive). Can you tell the average number of candies after M operations? I have written the below code in Python 3:

def operate(a, b, k, array):
    for i in range(a - 1, b):
        array[i] += k
def mean(array):
    return int(sum(array) / len(array))
splitinput = [int(x) for x in input().split()]
candy = []
for i in range(splitinput[0]):
    candy.append(0)
for j in range(splitinput[1]):
    splitinput2 = input().split()
    operate(int(splitinput2[0]), int(splitinput2[1]), int(splitinput2[2]), candy)
print(mean(candy))

It works, but times out on some test cases. How could I approach making this faster? I'm been coding in Python for a while, but the finer points of optimization still elude me.

Improve this question
2
  • The place to start with performance is to see what is the slowest. You should use a profiler: docs.python.org/2/library/profile.html though it may not be as useful in a small program like this Commented Feb 11, 2014 at 23:43
  • I would have done that, but I was fairly certain that the bottleneck was in the for j in range(splitinput[1]) part. Such programs can often be surprising, though, so I agree. Commented Feb 13, 2014 at 20:08

1 Answer 1

Reset to default
2

You don't care where the candies are. As long as you know how many candies there are and how many jars, you can compute the mean. Thus, you can just keep one count of all candies:

jars, ops = map(int, input().split())
candies = 0
for i in range(ops):
    a, b, k = map(int, input().split())
    candies += k*(b-a+1)
print candies / jars

This avoids having to keep track of N separate counts or increment k counters for each operation. When you get large k values, this is very important.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

It should be b - a + 1 though (SO won't let me edit less than 6 characters)
@rmartinjak: You're right. Fixed. The weird > characters in the question threw me off.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.