Pass It to the Driver#538

Solution

One pass can move the money at most positions toward the driver: there are then people between the sender and the recipient.

If passengers hold the money, there are passes including the final pass to the driver. These must cover n+1 positions, so (p+1)k \ge n+1.

The answer can be computed using integer division as (n+k)/k-1. Equivalently, it is , also using integer division.

Indeed, write n=qk+r, where 0 \le r < k. The money can pass through passengers: the first passes each cover positions, and the final pass to the driver covers r+1 \le k positions. Fewer passengers cannot suffice because passes cover at most qk \le n positions.

Complexity

The time complexity is and the extra space is .