Total Waiting Time for Handmade Items
Learn this problem
MicrosoftFULLTIMEOAProblem statement
There are N clients who have ordered N handmade items. The K-th client ordered exactly one item that takes T[K] hours to make. There is only one employee who makes items for clients, and they work in the following manner:
- spend one hour making the first item;
- if the item is finished, the employee delivers it to the client immediately;
- if the item is not finished, they put it after the N-th item for further work;
- the employee starts making the next item.
As the result may be large, return its last nine digits without leading zeros (in other words, return the result modulo 10^9).
Function
microsoftHandmadeItem(T: int[]) → intComplete the func in the editor 👉
that, given an array of integers T of length N, returns the total time that the clients need to wait (modulo 109).
Examples
Example 1
T = [3, 1, 2]return = 13The employee spends 6 hours making items in the following order: [1, 2, 3, 1, 3, 1]. The first client waited 6 hours for their item, the second client received their item after 2 hours and the third client after 5 hours. The total waiting time of all clients is 6 + 2 + 5 = 13.
Example 2
T = [1, 2, 3, 4]return = 24The employee prepares the items in the following order: 1, 2, 3, 4, 2, 3, 4, 3, 4, 4. The first client waited for 1 hour, the second client for 5 hours, the third client for 8 hours, and the fourth client for 10 hours. The total waiting time of all clients is 1 + 5 + 8 + 10 = 24 hours.
Example 3
T = [7, 7, 7]return = 60No explanation provided
Example 4
T = [10000]return = 10000No explanation provided
Constraints
N is an integer within the range [1..100,000]each element of array T is an integer within the range [1..10,000]