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?

@gre_gor - why did you remove the link to the original problem?? — user85421
– user85421, Commented Nov 8 at 8:27
@user85421 It should be clear without it. And it attracts crap answers ("here a code dump that gets a perfect score"). — gre_gor
– gre_gor, Commented Nov 8 at 8:29

trincot · Accepted Answer · 2025-11-08 07:17:45Z

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; } }

Collectives™ on Stack Overflow

Sometimes wrong output in Java queue simulation

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related