# Save the Prisoner Hackerrank problem solution coderinme

##### solution of Save the Prisoner hackerrank Problem

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.

Constraints
1<=T<=100
1<=N<=10^9
1<=M<=10^9
1<=S<=10^9

#### 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 S=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.

How we can solve it

In this problem, we need to determine the ID of last prisoner which can be done by moving M-1 steps further from S.
ID of last prisoner= (M-1+S)
Since we are moving in a circle so we need to take mod of this summation with N.
Because the ID starts from 1, so the ID of last prisoner= (M – 1 + S – 1) % N + 1)

#### Solution in C++ of Save the Prisoner

```#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int main() {

/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int t,no,m,sw,sd;
scanf("%d", &t);
for(int i=0; i<t; i++)
{
scanf("%d %d %d", &no, &m, &sw);
sd=(sw+m-1)% no;

if(sd==0)
printf("%d\n",no);
else
printf("%d\n",sd);
}

return 0;
}
```

#### Solution in python

``````x=int(raw_input())
for i in range(x):
[N,M,S]=[int(j) for j in raw_input().split()]
val= (N+M+S-1)%N
if val==0:
print N
else:
print val``````

#### Solution in C

``````#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int main() {
int t, n, m, s;
scanf("%d", &t);
while (t--) scanf("%d%d%d", &n, &m, &s), printf("%d\n", (m+s-2)%n+1);
return 0;
}
``````

#### Solution in java

``````import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int rounds = input.nextInt();
for(int i = 0; i < rounds; i++)
{
int num = input.nextInt();
int lop = input.nextInt();
int s = input.nextInt() - 1;
while(lop != 0)
{
lop--;
s++;
if(s > num)
s = 1;
}
System.out.println(s);
}
}
}``````

All rights reserved. No part of this Post may be copied, distributed, or transmitted in any form or by any means, without the prior written permission of the website admin, except in the case of brief quotations embodied in critical reviews and certain other noncommercial uses permitted by copyright law. For permission requests, write to the owner, addressed “Attention: Permissions Coordinator,” to the admin@coderinme.com

### hasectic

A web developer(Front end and Back end), and DBA at csdamu.com. Currently working as Salesforce Developer @ Tech Matrix IT Consulting Private Limited. Check me @about.me/s.saifi