Sponsored
Sponsored
This approach simulates the process of each person buying their tickets. We keep track of the time spent and decrement the ticket count from each person one at a time until the k-th person has purchased all their tickets.
Time Complexity: O(n * max(tickets)) where max(tickets) is the maximum tickets any person wants to buy.
Space Complexity: O(1)
1#include <stdio.h>
2
3int timeToBuyTickets(int* tickets, int ticketsSize, int k) {
4 int time = 0;
5 for (int i = 0; ; i = (i + 1) % ticketsSize) {
6 if (tickets[i] > 0) {
7 tickets[i]--;
8 time++;
9 if (i == k && tickets[k] == 0) return time;
10 }
11 }
12}
13
14int main() {
15 int tickets[] = {2, 3, 2};
16 int k = 2;
17 printf("Time taken: %d\n", timeToBuyTickets(tickets, 3, k));
18 return 0;
19}We continuously loop through the array, simulating each person buying one ticket at a time if they have tickets remaining. We check after each purchase if the target person (k-th) has finished buying their tickets.
This approach avoids the simulation by calculating the total time taken mathematically. For this, we traverse through each person and calculate the time based on the number of people in the queue and the minimum value between their current tickets and the tickets needed by k-th person.
Time Complexity: O(n)
Space Complexity: O(1)
1
Python's clarity helps in implementing the mathematical approach, making the calculation of each person's purchase time efficiently.