C++ :
int saveThePrisoner(int n, int m, int s) {
int prisonerNo = s, remainder = 0;
remainder = m % n;
prisonerNo = prisonerNo - 1 + remainder;
if(prisonerNo > n){
prisonerNo -= n;
}
if(prisonerNo == 0){
prisonerNo = n;
}
return prisonerNo;
}Explanation:
It is tempting to simply use an outer for loop (to pass candy around the prisoners), then followed by an inner while loop (to subtract prisoners after each round if the candy go more than 1 round) during a first glance at the question, since that is the way the question is described. Don’t! This will result in a (O³) solution due to the main function running a single for loop to go through the test cases. Having an O³ solution is extremely inefficient and will result in a ‘Terminated due to time out’ status.
Get the remainder, which is the number of sweets left over and not passed in a complete round, by using m (number of sweets) % n (total number of prisoners). Calculate the final prisoner number by adding the remainder to the original number of the prisoner which the passing of sweets started from (s).
Check if the final prisoner number becomes greater than the total number of prisoners (n), if this happens, deduct a complete round of prisoners from prisonerNo to get the actual number.
The final if checks for situations where number of sweets m % total number of prisoners n is 0, and that the passing starts from prisoner number 1. In this case, prisonerNo becomes 1 – 1 + 0, which is 0. In this case, assign prisonerNo to the last prisoner to receive the candy, which is n.
