Repository

https://github.com/enyason/SaveThePrisoner

What Will I Learn?

• Develop an Simple Algorithm to solve the problem
• Code the Algorithm using Java

Requirements

• System Requirements : Java JDK, Eclipse IDE or Netbeans IDE
• OS Support for Java : Windows, mac OS, Linux
• Required Knowledge : A fair knowledge of Java

Resources for Java and this tutorial

• 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

Difficulty

• Basic

Tutorial Duration 30- 35 Minutes

Tutorial Content

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):

• n: an integer, the number of prisoners
• m: an integer, the number of sweets
• s: an integer, the chair number to begin passing out sweets from

Constraints

STEP 1 : Problem Analysis

The Save the Prisoner Problem has 3 parameters to play with:

1. Number of prisoners (n)
2. Number of sweet (m)
3. Number to begin passing sweet (s)

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.

• Case 1 - warn prisoner at seat 3
• Case 2 - warn prisoner at seat 4
• Case 3 - warn prisoner at seat 5
• Case 4 - warn prisoner at seat 1

STEP 2 : Definition Terms

There are some terms that will help us solve this problems, so lets take note of them:

1. The start position s
2. The last position
3. The number of prisoners n
4. The number of sweet m
5. The remainder : The remainder is the number of sweets left after it had been evenly distributed

STEP 3 : Identify Start Position Possibilities

By observation we conclude that the starting position has only two possibilities :

1. S = 1 or
2. S > 1

STEP 4 : Evaluate Case S = 1

When the starting position = 1, there are only two conditions that exist

1. When the remainder = 0

2. 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

STEP 5 : Evaluate Case S > 1

In this case, 2 conditions still holds:

1. When remainder = 0

2. When remainder !=0

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

remainder != 0

When remainder != 0, two conditions holds in it. To help us understand this, lets consider the following:

• The seat to be warned will be the last term + the remainder (Lt + rem)

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

• Downside to seat = Lt + rem

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

• We should not use Lt + rem when the remainder crosses the boundary.
• We should rather get the part of the remainder that is contained in the first part of the seats using Mathabs(Lt - n). Here we are using (Lt - n) because the size of the second part is the value of the last term, hence, the difference between the last term and the number of prisoners, will give a value for the remainder contained in the first part.
• Now we know the remainder o both parts, we then subtract the remainder from part 1 from the entire remainder. This works fine because the prisoners are ordered sequentially.

STEP 6 : Implement in Java Code

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

https://github.com/enyason/SaveThePrisoner