Repository
https://github.com/enyason/SaveThePrisoner
Oracle Website: https://www.oracle.com/index.html
Java Docs : http://www.oracle.com/technetwork/java/javase/documentation/api-jsp-136079.html
HackerRank : https://www.hackerrank.com/challenges/save-the-prisoner/problem
In this tutorial, we are going to solve the coding Challenge posted on Hackerrank .
Problem
A jail has a number of prisoners and a number of treats to pass out to them. Their jailer decides the fairest way to divide the treats is to seat the prisoners around a circular table in sequentially numbered chairs. A chair number will be drawn from a hat. Beginning with the prisoner in that chair, one candy will be handed to each prisoner sequentially around the table until all have been distributed.
The jailer is playing a little joke, though. The last piece of candy looks like all the others, but it tastes awful. Determine the chair number occupied by the prisoner who will receive that candy.
For example, there are prisoners and pieces of candy. The prisoners arrange themselves in seats numbered 1 to 4 . Let's suppose two is drawn from the hat. Prisoners receive candy at positions 2,3,4,1,2,3 . The prisoner to be warned sits in chair number 3.
Function Description
Complete the saveThePrisoner function in the editor below. It should return an integer representing the chair number of the prisoner to warn.
saveThePrisoner has the following parameter(s):
Constraints
The Save the Prisoner Problem has 3 parameters to play with:
Note :
S can be any value from 1 to n. This is as a result of the number drawn from the hat. The number of sweets m is not dependent on n. It can be <,=, or > than n. Same with n, it is not dependent on m. It can be =,> or < m.
Our goal primarily is to determine the prisoner that will receive the last candy. But then, the starting position is not always 1. Lets first take 5 prisoners and give them different starting position at different instances, with number of sweets = 8
Observation :
From the image above, we observe that the starting position changes. It is not always at 1 hence the prisoner to warn is different at different instances.
There are some terms that will help us solve this problems, so lets take note of them:
By observation we conclude that the starting position has only two possibilities :
When the starting position = 1, there are only two conditions that exist
When the remainder = 0
When the remainder != 0
If condition 1 holds, the seat to be warned will be the last seat. seat = n
if condition 2 holds, the seat to be warned will be seat. seat = rem
In this case, 2 conditions still holds:
When remainder = 0
When remainder !=0
When remainder = 0, he seat to be warned will be the last seat. seat = s -1
Why seat = s -1 ?
With the starting position always greater than 1 in this case, and considering how the prisoners are numbered sequentially, the last position will always be the previous value of the start position = s-1
When remainder != 0, two conditions holds in it. To help us understand this, lets consider the following:
Why Lt + rem ?
In the image above,the seats are divided into two parts. The first part is where the last seat falls and the other part is where the first seat falls. The values in the second part are always > those in the second part. Since the prisoners are numbered sequentially, we can add Lt and rem to get the seat number of the prisoner to warn
Lt + rem looks good but it is not true for all cases. Observe the image below for more insight.
From the image above, we see that the seat to warn should be 2 and 1 but we are get 7 and 6 using Lt + rem.
To Handle this , we need to be aware of the boundary between the two parts
public class SaveThePrisoner {
public static void main(String[] args) {
int n = 15;
int m = 20;
int s = 4;
int lt, seat, lMinusN;
int rem = m % n;
if (s == 1) {
if (rem == 0) {
seat = n;
} else {
seat = rem;
}
} else {
lt = s - 1;
if (rem == 0) {
seat = lt;
}
else {
int temp = lt + rem;
if (temp <= n) {
seat = temp;
} else {
lMinusN = Math.abs(lt - n);
seat = rem - lMinusN;
}
}
}
System.out.println("warn seat " + seat);
}
}
Reading steps 1 to 5 will give u a better understanding of the the code block above. Basically u see all the cases we identified in step 3 is handled with an if statement. Using a Nested IF-ELSE statement from my test proved to be efficient compared to an algorithm that tries to spot the seat number in a loop.
The code can be tested on multiple Test Cases on the HackeRrank site https://www.hackerrank.com/challenges/save-the-prisoner/problem
Proof of Work The complete source code can be found on gitHub