Save the Prisoner

A jail has prisoners, and each prisoner has a unique id number, S, ranging from 1 to N. There are M sweets that must be distributed to the prisoners.

The jailer decides the fairest way to do this is by sitting the prisoners down in a circle (ordered by ascending S), and then, starting with some random S, distribute one candy at a time to each sequentially numbered prisoner until all M candies are distributed. For example, if the jailer picks prisoner S = 2, then his distribution order would be (2, 3, 4, 5, ..., n-1, n, 1, 2, 3, 4, ...) until all sweets are distributed.

But wait—there's a catch—the very last sweet is poisoned! Find and print the ID number of the last prisoner to receive a sweet so he can be warned.

Input Format

The first line contains an integer, T, denoting the number of test cases.
The T subsequent lines each contain 3 space-separated integers:
N (the number of prisoners), M (the number of sweets), and S (the prisoner ID), respectively.

Output Format

For each test case, print the ID number of the prisoner who receives the poisoned sweet on a new line.

Sample Input

1
5 2 1

Sample Output

2

My solution:

test_cases = int(input())

for _ in range(test_cases):
    n, m, s = map(int, input().split())

    while m > 0:
        m -= 1
        s = n if s > n else s + 1

    s = n if s < 1 else s - 1
    print(s)

I think big-O can be very large since M could be up to 10^9. When I test with M = 10^9, my terminal "killed" so please help!

use variable names that mean something

I can't keep track of whether n is the number of sweets or the number of prisoners because it is a single letter that doesn't mean much. Maybe s is for sweets? No it probably means "start". Bah! So confusing. Using words that mean something makes for better variable names for humans.

So

prisoners = n
sweets = m
first_prisoner = s

Now I can follow what's happening.

use modulus!

As Billyoyo put it:


You have a clock with N hours on it, the hand is currently pointed at x. Where will the hand be pointing in M hours?

which is an excellent hint. If you're thinking about things that are periodic modulus will very likely come in handy.

Let's start by figuring out how many sweets are left after all of the prisoners get an even numbers

odd_sweets = sweets % prisoners

So if we have 250 sweets and 200 prisoners there are 50 odd_sweets. If we have 400 sweets and 200 prisoners there are 0 odd_sweets since the candies were evenly distributed. Even if there aren't enough sweets to go around once modulus will still give you the right number. So if we have 1000 prisoners and 400 sweets (mean bums) there would be 400 odd_sweets since you wouldn't have been able to around one entire time so they're all "odd".

Then we want to know which prisoner got the last treat

sick_prisoner = (first_prisoner + odd_sweets) % prisoners

We start by adding the number of odd_sweets to the ID of the first prisoner. If those add up to less than the number of prisoners life is good and we didn't loop around. But if we get a number that is bigger than the number of prisoners we need to bring it back into range which the modulus will conveniently do for us.

So if we have 50 odd_sweets and 200 prisoners and the first_prisoners

• = 20 then 50+20 = 70 and we're good

• = 180 then 50+180 = 230 which is too big, but then after doing 230%200 we end up with 30 which makes sense

With that the entire calculation can be handled without internal loops.

StackExchange Code Review Q#135677, answer score: 8