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 <= 109Problem Overview: Each student consumes a fixed number of chalk pieces from an array while answering questions in order. When the chalk runs out mid-cycle, the student who cannot take their required amount must replace it. The task is to identify that student index efficiently even when k is very large.
Approach 1: Cyclic Reduction using Total Sum (O(n) time, O(1) space)
The key observation: the process repeats in cycles. If the total chalk consumption of one full round is sum(chalk), then after every complete cycle the same sequence repeats. Instead of simulating potentially billions of steps, compute k % totalSum. This reduces the problem to the remaining chalk within a single cycle. Iterate through the array, subtract each student's requirement from the remainder, and return the first index where the remainder becomes smaller than the required chalk. This approach is optimal in practice because it avoids extra memory and only scans the array once.
Approach 2: Binary Search on Prefix Sums (O(n) build + O(log n) query time, O(n) space)
Another strategy models the cumulative chalk usage. Build a prefix sum array where prefix[i] represents the total chalk used by students 0..i. Reduce k using k % totalSum to stay within a single cycle. The goal becomes finding the first prefix value greater than the remaining chalk. Because the prefix array is strictly increasing, apply binary search to locate the smallest index where prefix[i] > remaining. That index corresponds to the student who needs to replace the chalk. This approach is useful when the prefix array may be reused for multiple queries.
Recommended for interviews: The cyclic reduction approach is what most interviewers expect. It demonstrates pattern recognition—identifying a repeating process and eliminating unnecessary simulation. The prefix-sum + binary-search solution shows deeper algorithmic thinking and is useful when handling repeated queries or when cumulative data structures are already present.
This approach takes advantage of the cyclical nature of the problem. Initially, the teacher provides problems to each student in sequence. We calculate the total sum of chalk required for one full pass through the students. If k is greater than this sum, it implies that the whole cycle can be repeated multiple times. Therefore, we reduce k by this sum repeatedly to get only the relevant chalk pieces needed as a remainder, then find the student who will run out of chalk.
The Python solution first calculates the total chalk used per cycle, then updates k to be k modulo this total. It then iterates through the students to identify the first one that does not have enough chalk for their problem, thereby having their index returned.
Python
C++
Java
C#
JavaScript
Time Complexity: O(n), where n is the number of students since we iterate over the chalk array twice, once to find the total chalk and then to find the replacer.
Space Complexity: O(1) as we use only a constant amount of extra space.
This approach accumulates a prefix sum of chalk costs as an extra preprocessing step. With prefix sums, one can quickly determine the range that k falls into using binary search, leading to the index of the student who will run out of chalk.
In this Python solution, the prefix sum of the chalk array allows a binary search to find the appropriate student when a sufficient chalk cycle is calculated out of k using modulo. Binary search helps efficiently navigate the prefix sums.
Python
C++
Java
C#
JavaScript
Time Complexity: O(n log n) due to sorting and binary search.
Space Complexity: O(n) for the prefix sums array.
Since the students' answers are conducted in rounds, we can add up the chalk needed by all students to get a total s. Then we take the remainder of k by s, which can tell us the remaining number of chalks after the last round.
Next, we just need to simulate the last round. Initially, the remaining number of chalks is k, and the student with the number 0 starts to answer the question. When the remaining number of chalks is less than the current student needs, the current student needs to replenish the chalk, and we directly return the current student's number i. Otherwise, we subtract the chalk needed by the current student from the remaining chalk, and add one to the current student's number i for the next simulation.
The time complexity is O(n), where n is the number of students. The space complexity is O(1).
| Approach | Complexity |
|---|---|
| Cyclic Reduction using Total Sum | Time Complexity: O(n), where n is the number of students since we iterate over the chalk array twice, once to find the total chalk and then to find the replacer. |
| Binary Search on Prefix Sums | Time Complexity: O(n log n) due to sorting and binary search. |
| Sum and Modulo + Simulation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Cyclic Reduction using Total Sum | O(n) | O(1) | Best general solution when only one query exists and minimal memory usage is preferred |
| Prefix Sum + Binary Search | O(n) preprocessing + O(log n) search | O(n) | Useful when prefix sums are reused or when practicing binary search on cumulative arrays |
Find the Student that Will Replace the Chalk | 2 Ways | Leetcode 1894 | codestorywithMIK • codestorywithMIK • 6,342 views views
Watch 9 more video solutions →Practice Find the Student that Will Replace the Chalk with our built-in code editor and test cases.
Practice on FleetCode