Recent Tutorials and Articles
    HackerRank Solution: Save the Prisoner!
    Published on: 15th July 2016

    This tutorial provides Java and Python solution to "Save the Prisoner!" problem of Hackerrank.

    Hackerrank Challenge Details


    Problem Statement:

    A jail has N 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 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?

    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

    Explanation:

    There are N = 5 prisoners and M = 2 sweets. Distribution starts at ID number S = 1, so prisoner 1 gets the first sweet and prisoner 2 gets the second (last) sweet. Thus, we must warn prisoner 2 about the poison, so we print 2 on a new line.

    Solution Details


    Java Implementation:

    package com.saintech.allprogtutorials.hackerrank.algos;
    
    import java.util.Scanner;
    
    /**
     * @author Sain Technology Solutions
     *
     * Solution to Problem - https://www.hackerrank.com/challenges/save-the-prisoner
     */
    public class SavePrisoner {
    	
    	private static int getConcernedPrisoner(int N, int M, int S) {
    		final int prisonerId = (S + (M - 1)) % N;
    		//if prisonerId comes as 0 means we are talking about Nth as Mod will never give us N
    		return prisonerId == 0 ? N : prisonerId;
    	}
    	
    	public static void main(String[] args) {
    		final Scanner in = new Scanner(System.in);
    		final int T = Integer.parseInt(in.next());
    		for(int i = 0; i < T; i++) {
    			final int N = Integer.parseInt(in.next());
    			final int M =  Integer.parseInt(in.next());
    			final int S = Integer.parseInt(in.next());
    			System.out.println(getConcernedPrisoner(N, M, S));
    		}
    		in.close();
    	}
    }

    Thank you for reading through the tutorial. In case of any feedback/questions/concerns, you can communicate same to us through your comments and we shall get back to you as soon as possible.

    Published on: 15th July 2016