Hackerrank: Save the Prisoner

Question

I am facing a problem in modular arithmetic.

Simplified problem statement:

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

The prisoners are seated around a circular table in sequentially numbered chairs (numbering starts from 1).

Find the prisoner who receives the last sweet.

I can think of many possible solutions but decided to try a one liner:

m % n + s - 1

My reasoning:

1. Distribute m sweets to n prisoners evenly. The remainder will be part of the last round of distribution.

2. Add the initial offset s to reach the last seat.

3. I had to subtract 1 from the result to pass some test cases (I don't know the reason).

However, the formula fails for other test cases.

What is going wrong in the logic? How should I correct the formula?

Answer 1

The reason you have to subtract $1$ is to avoid what is known as a fencepost error or "off-by-one" error. Suppose there is only $1$ sweet. Then starting at seat $s$ you know the last (and only) sweet will go to the pirsoner at seat $s$. But $m\%n+s$ gives the result $s+1$. You need the $-1$ adjustment in $m\%n+s-1$ to account for the fact that sweet $1$ is given to the prisoner at setat $s$, not at seat $s+1$.

The other thing you have to remember is that $m\%n$ gives a result between $0$ and $n-1$, so $m\%n+s-1$ will be between $s-1$ and $n+s-2$. But the seat numbers go from $1$ to $n$. You could adjust your formula to $(m+s-1)\%n$, which is correct most of the time, but gives the incorrect answer $0$ when $m+s-1$ is a multiple of $n$. I'll leave you to think about how to make another adjustment to this expression to get an answer that is correct in all cases.

Answer 2

I have got (m + s - 1) % n ? (m + s - 1) % n : n; following the explanations of John and Gandal.

However, I was able to shorten it further using the concept of Fencepost Error introduced to me by Gandal.

1. This is obvious by now:

   (m + s - 1) % n

2. % outputs in the range:

   [0, n-1]

3. So, convert all the quantities in the operand with respect to counting from zero:

   ((m - 1) + (s - 1)) % n

4. Then convert that answer with respect to counting from one:

   (((m - 1) + (s - 1)) % n) + 1

The final solution has passed all the test cases.

It is still short and a one-liner:

(m + s - 2) % n + 1