FastPrep

Description

Solutions

Submission

Total Waiting Time for Handmade Items

🔥 FULLTIME

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 Description

Complete 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 10⁹).

Example 1:

Input:  T = [3, 1, 2]
Output: 13 
Explanation:
The 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:

Input:  T = [1, 2, 3, 4]
Output: 24 
Explanation:
The 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:

Input:  T = [7, 7, 7]
Output: 60 
Explanation:
No explanation provided

Example 4:

Input:  T = [10000]
Output: 10000 
Explanation:
No 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]