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 <iostream>
2#include <vector>
3using namespace std;
4
5int timeToBuyTickets(vector<int>& tickets, int k) {
6 int time = 0;
7 for (int i = 0; ; i = (i + 1) % tickets.size()) {
8 if (tickets[i] > 0) {
9 tickets[i]--;
10 time++;
11 if (i == k && tickets[k] == 0) return time;
12 }
13 }
14}
15
16int main() {
17 vector<int> tickets = {2, 3, 2};
18 int k = 2;
19 cout << "Time taken: " << timeToBuyTickets(tickets, k) << endl;
20 return 0;
21}Similar to the C solution, we simulate each ticket purchase with a loop until the k-th person has no tickets left. The use of vector allows dynamic sizing of the queue.
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
class TicketBuying {
public static int TimeToBuyTickets(int[] tickets, int k) {
int time = 0;
for (int i = 0; i < tickets.Length; i++) {
time += i <= k ? Math.Min(tickets[i], tickets[k]) : Math.Min(tickets[i], tickets[k] - 1);
}
return time;
}
static void Main() {
int[] tickets = {5, 1, 1, 1};
int k = 0;
Console.WriteLine("Time taken: " + TimeToBuyTickets(tickets, k));
}
}C# version effectively calculates the same logic by iterating through the array and figuring out the purchase time based on positions and ticket requirements.