Logo
IconChallenge
Icon
IconProblem
IconSolutions
IconSubmissions

Time Needed to Buy Tickets

XPChallenge Points: 10
levelLevel: Easy

There are n people in a queue. Person i needs tickets[i] tickets, buying one per second. After buying a ticket, they go to the end of the line instantly; if they’re done, they leave.
Return the total seconds until the person originally at index k finishes buying all their tickets.

Key formula (O(n)):
Let t = tickets[k]. Then the answer is

i=0kmin(tickets[i],t)  +  i=k+1n1min(tickets[i],t1).\sum_{i=0}^{k} \min(tickets[i],\, t)\;+\;\sum_{i=k+1}^{n-1} \min(tickets[i],\, t-1).

People at or before k get served t times while k is present; those after k get at most t-1 turns before k’s last ticket.

Example 1:

Input: tickets = [2,3,2], k = 2

Output: 6

Example 2:

Input: tickets = [5,1,1,1], k = 0

Output: 8

Example 3:

Input: tickets = [1], k = 0

Output: 1

to Continue
like
dislike

Accepted:

Submission:

IconReport an issue
Icon
IconCode
IconYou need toto run or submitYou need toto run or submit
IconTest Case
IconTest Result