A Hospital has N Patients, and each prisoner has a unique id number, S, ranging from 1 to N. There are M sweets that must be distributed to the Patients.
The Warden decides the fairest way to do this is by sitting the Patients 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 Warden picks prisoner S = 2, then his distribution order would be (2, 3, 4, 5,..., n-1, n, 1, 2, 3, 4,...) until all M sweets are distributed.
But wait —there's a catch—the very last sweet is poisoned! Can you find and print the ID number of the last prisoner to receive a sweet so he can be warned?
Solution
Let us take an example to solve this problem –
We can use modulo to solve this problem. As we know if the number of sweets is more than the number of Patients the process of distribution will be repeated. Hence we can use modulo to after distribution repeatedly as -
Remaining_sweets = M%N = 2
for above question Remaining_sweets = 14%12 = 2
Now we need to focus to distribute the remaining items from the initial position.
This can be again achieved using modulo as -
Patient_in_danger = (first_Patient + remaining_sweets -1) % number_of_Patients
Patient_in_danger = (2 + 2 - 1) % 12 = 3
Revalidate the above by manually distributing the sweets to Patient.
The Warden decides the fairest way to do this is by sitting the Patients 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 Warden picks prisoner S = 2, then his distribution order would be (2, 3, 4, 5,..., n-1, n, 1, 2, 3, 4,...) until all M sweets are distributed.
But wait —there's a catch—the very last sweet is poisoned! Can you find and print the ID number of the last prisoner to receive a sweet so he can be warned?
Solution
Let us take an example to solve this problem –
We can use modulo to solve this problem. As we know if the number of sweets is more than the number of Patients the process of distribution will be repeated. Hence we can use modulo to after distribution repeatedly as -
Remaining_sweets = M%N = 2
for above question Remaining_sweets = 14%12 = 2
Now we need to focus to distribute the remaining items from the initial position.
This can be again achieved using modulo as -
Patient_in_danger = (first_Patient + remaining_sweets -1) % number_of_Patients
Patient_in_danger = (2 + 2 - 1) % 12 = 3
Revalidate the above by manually distributing the sweets to Patient.
