I've been given a task that I had issue solving.
John likes jumping so he is about to build a new jumping terrain. The terrain consists of N blocks, and in each block he can put multiple jumping marks. He starts by jumping from the ground on some mark from the first block, then on some mark in the second block, and so on until he finally jumps from some mark from the N-th block back to the ground.
John has bought N boxes of jumping marks (i-th box contains ci marks). He has put them into the cart and now he is moving from the first block to last one. He wants to assign each box to distinct block. After that, for each box he will put all marks from the box into respective block.
He is not aware that while setting up the terrain, Mark is hiding between boxes and steals one jumping mark from each box that is left in the cart every time the cart moves to next position (excluding the first position).
John wants to build such a terrain that the number of ways to jump from the beginning to the end of the terrain is maximum possible.
Help Ivan find out the best arrangement of the boxes to achieve the maximum number of ways he can jump the terrain if he places the boxes in the correct order.
For example, given an array
[2, 4, 4, 1], solution is 2 (correct order is
[1, 2, 4, 4], which because of Mark turns to
[1, 1, 2, 1], and there are two ways to traverse that array). For
[1, 1] solution is 0. For
[3,3,3] solution is 6.
At first I thought this is a simple matter, but feedback I got from my instructor told me that solution was unsatisfying.
Here is my solution:
def solution(a): # a is input array n = len(a) a.sort() c = 1 result = a for i in range(1, n): v = a[i] - c if v < 1: return 0 c += 1 result *= v return result % ((10 ** 9) + 7)
What is wrong with this solution?