Find the Student that Will Replace the Chalk
MedPrompt
There are n students in a class numbered from 0 to n - 1. The teacher will give each student a problem starting with the student number 0, then the student number 1, and so on until the teacher reaches the student number n - 1. After that, the teacher will restart the process, starting with the student number 0 again.
You are given a 0-indexed integer array chalk and an integer k. There are initially k pieces of chalk. When the student number i is given a problem to solve, they will use chalk[i] pieces of chalk to solve that problem. However, if the current number of chalk pieces is strictly less than chalk[i], then the student number i will be asked to replace the chalk.
Return the index of the student that will replace the chalk pieces.
Example 1:
Input: chalk = [5,1,5], k = 22
Output: 0
Explanation: The students go in turns as follows:
- Student number 0 uses 5 chalk, so k = 17.
- Student number 1 uses 1 chalk, so k = 16.
- Student number 2 uses 5 chalk, so k = 11.
- Student number 0 uses 5 chalk, so k = 6.
- Student number 1 uses 1 chalk, so k = 5.
- Student number 2 uses 5 chalk, so k = 0.
Student number 0 does not have enough chalk, so they will have to replace it.Example 2:
Input: chalk = [3,4,1,2], k = 25
Output: 1
Explanation: The students go in turns as follows:
- Student number 0 uses 3 chalk so k = 22.
- Student number 1 uses 4 chalk so k = 18.
- Student number 2 uses 1 chalk so k = 17.
- Student number 3 uses 2 chalk so k = 15.
- Student number 0 uses 3 chalk so k = 12.
- Student number 1 uses 4 chalk so k = 8.
- Student number 2 uses 1 chalk so k = 7.
- Student number 3 uses 2 chalk so k = 5.
- Student number 0 uses 3 chalk so k = 2.
Student number 1 does not have enough chalk, so they will have to replace it.
Constraints:
chalk.length == n1 <= n <= 1051 <= chalk[i] <= 1051 <= k <= 109
Approaches
3 approaches with complexity analysis and trade-offs.
This approach directly simulates the process described in the problem. We iterate through the students in a cycle, subtracting the chalk used by each student from the total k. The simulation stops when a student does not have enough chalk, and that student's index is returned.
Algorithm
- Initialize an index
i = 0. - Start a
while(true)loop to simulate the process indefinitely. - Inside the loop, check if the remaining chalk
kis strictly less than the chalk required by the current student,chalk[i]. - If
k < chalk[i], this student cannot take their turn and must replace the chalk. Return the student's indexi. - If there is enough chalk, subtract
chalk[i]fromk. - Move to the next student by updating the index:
i = (i + 1) % n.
Walkthrough
We use a loop that continuously cycles through the student indices from 0 to n-1. An index variable, say i, keeps track of the current student. In each iteration, we check if the remaining chalk k is less than chalk[i]. If it is, student i cannot solve the problem and must replace the chalk, so we return i. Otherwise, we update k by subtracting chalk[i] and move to the next student by updating i to (i + 1) % n. This process continues until the condition k < chalk[i] is met.
class Solution { public int chalkReplacer(int[] chalk, int k) { int n = chalk.length; int i = 0; while (true) { if (k < chalk[i]) { return i; } k -= chalk[i]; i = (i + 1) % n; } }}Complexity
Time
O(k). The number of iterations is proportional to `k` divided by the average chalk value. In the worst-case scenario where chalk values are small, the loop runs approximately `k` times. Given `k` can be up to `10^9`, this is too slow.
Space
O(1). We only use a few variables to store the index and the remaining chalk, so the space used is constant.
Trade-offs
Pros
Very simple to understand and implement as it follows the problem description literally.
Cons
The time complexity is dependent on the value of
k, which can be very large (10^9), leading to a Time Limit Exceeded (TLE) error on most platforms.
Solutions
Solution
class Solution {public int chalkReplacer(int[] chalk, int k) { long s = 0; for (int x : chalk) { s += x; } k %= s; for (int i = 0;; ++i) { if (k < chalk[i]) { return i; } k -= chalk[i]; } }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.