Sometimes wrong output in Java queue simulation

Question

Problem summary:
Each person in line has tickets[i] tickets to buy. Every second

• The person at the front buys one ticket.

• If they still need more tickets, they move to the end of the queue.

We need to find how many seconds it takes for the person at index k to finish buying their tickets.

My code:

public int timeRequiredToBuy(int[] tickets, int k) {
 Queue<Integer> queue = new LinkedList<>();
 for (int i = 0; i < tickets.length; i++) {
 queue.add(i);
 }
 int time = 0;
 while (!queue.isEmpty()) {
 int person = queue.poll();
 if (!queue.isEmpty()) {
 tickets[queue.peek()]--;
 } else {
 tickets[person]--;
 }
 time++;
 if (tickets[person] > 0) {
 queue.add(person);
 }
 if (person == k && tickets[person] == 0) {
 break;
 }
 }
 return time;
}

tickets =
[83,86,38,31,59,25,89,71,54,71,84]
k =1
Output
688
Expected
687

Why does this logic result in a value that is higher than the expected one? How would I correctly track the tickets for each person without accidentally decrementing the wrong one?

• user85421: @gre_gor - why did you remove the link to the original problem??
• gre_gor: @user85421 It should be clear without it. And it attracts crap answers ("here a code dump that gets a perfect score").

Answer 1

The problem is in this part:

 if (!queue.isEmpty()) {
 tickets[queue.peek()]--;
 } else {
 tickets[person]--;
 }

There is no reason to make this distinction. Each iteration of the loop should only touch the number of tickets of the person that was taken from the queue, not of the next entry in the queue -- that will be dealt with in the next iteration.

So eliminate that distinction, and just do:

 tickets[person]--;

Note that although this will work, the goal of the challenge is probably to look for a more efficient algorithm.

Hint for a more efficient approach:

How many times will the person at index i buy a ticket, (a) when i < k, (b) when i = k, and (c) when i > k?

Efficient solution:

class Solution { public int timeRequiredToBuy(int[] tickets, int k) { int numTickets = tickets[k]; int time = 0; for (int i = 0; i < tickets.length; i++) { time += i != k ? Math.min(tickets[i], numTickets) : numTickets--; // Decrement once we arrive at k } return time; } }