CODEWITHSUNDEEP
algorithmperformancepython-3.xoptimizationdynamic-programming
Equinox
Equinox

Reputation: 6758

HackerRank Candies distribution

Problem statement

Alice wants to give some candies to the children in her class. All the children sit in a line ( their positions are fixed), and each of them has a rating score according to his or her performance in the class. Alice wants to give at least 1 candy to each child. If two children sit next to each other, then the one with the higher rating must get more candies. Alice wants to save money, so she needs to minimize the total number of candies given to the children.

Output a single line containing the minimum number of candies Alice must buy.

HackerRank problem link

Sample Input

3  (no of students )
1  (individual scores)
2  
2

Sample Output

4

my solution:

arr = []
for i in range(int(input())):
    arr.append(int(input()))

# candy left to right, candy right to left, and candy array
candy_lr = [1]*(len(arr))
candy_rl = [1]*(len(arr))
candy = []

# traverses from left to right and assigns candy to students
for i in range(1,len(arr)):
    if arr[i]>arr[i-1]:
        candy_lr[i] = candy_lr[i-1]+1

# traverses from right to left and assigns candy to students        
for i in range(len(arr)-2,0,-1):
    if arr[i]>arr[i+1]:
        candy_rl[i] = candy_rl[i+1]+1   

#calculates the total candy needed
for i in range(0,len(arr)):
    candy.append(max(candy_lr[i],candy_rl[i]))
print(sum(candy))

However this solution passes only 11/15 test cases. here is a sample input. For the above input the output should be 33556 but my output is 33555 and in all the 4 failed test case my output differs from expected output by 1. I tried it with pen and paper for 15 elements and its working fine. Is there any corner case I am missing ?

Upvotes: 1

Views: 6628

Answers (1)

Abhishek Bansal
Abhishek Bansal

Reputation: 12705

Your code has an index error. The range function does not include the final index.

for i in range(len(arr)-2,0,-1):

Should be

for i in range(len(arr)-2,-1,-1):

Eg: For an input of

3
2
1
1

your code outputs 3 when the correct answer is 4.

Upvotes: 2

Related Questions