Find the Student that Will Replace the Chalk: Prefix Sum Meets Binary Search

A teacher walks around the classroom in a circle, handing chalk to each student in order. Each student uses a specific amount and passes the chalk along. Eventually the chalk runs out mid-round, and one student gets stuck replacing it. Your job: figure out which student that is.

This is LeetCode 1894: Find the Student that Will Replace the Chalk, and it is a great example of how combining two simple ideas (prefix sums and binary search) can turn a brute-force simulation into an efficient one-pass solution.

The problem

You are given an array chalk where chalk[i] is the amount of chalk student i uses each round. You are also given an integer k, the total pieces of chalk available. Students use chalk in order starting from index 0. When the last student finishes, it wraps back to student 0. The process repeats until some student does not have enough chalk left to use their full amount. Return the index of that student.

Example: chalk = [5, 1, 4, 2, 3], k = 22.

One full round uses 5 + 1 + 4 + 2 + 3 = 15 pieces. After one complete round, 22 - 15 = 7 pieces remain. In the next partial round: student 0 uses 5 (leaving 2), student 1 uses 1 (leaving 1), and student 2 needs 4 but only 1 is left. Student 2 has to go replace the chalk. The answer is 2.

The brute force approach

The most direct approach is to simulate the process. Walk through each student, subtract their chalk usage from k, and stop when k drops below the current student's requirement.

def chalk_replacer_brute(chalk, k):
    n = len(chalk)
    while True:
        for i in range(n):
            if k < chalk[i]:
                return i
            k -= chalk[i]

This works, but if k is very large relative to the total chalk per round, you end up looping through the array many times doing the same work. With k up to 10^9 and chalk summing to a small number, this could take billions of iterations. We need something smarter.

The optimized approach

The key observation: every full round through all students uses exactly the same amount of chalk. So instead of simulating round after round, you can skip all the full rounds at once using modulo arithmetic. Then you only need to figure out where in the partial round the chalk runs out, and that is where prefix sums and binary search come in.

Here is the plan:

1. Compute the prefix sum array. prefix[i] is the total chalk used by students 0 through i. The last value, prefix[n-1], is the total chalk consumed per round.

2. Take k % prefix[n-1]. This gives you the remaining chalk after all complete rounds are stripped away. Call this the remainder.

3. Binary search the prefix array for the first index where prefix[i] is greater than the remainder. That student is the one who cannot finish, because the cumulative usage up to and including that student exceeds the available chalk.

This runs in O(n) to build the prefix sum and O(log n) for the binary search. No wasted simulation loops.

Visual walkthrough

The code

from bisect import bisect_right

def chalk_replacer(chalk, k):
    n = len(chalk)
    prefix = [0] * n
    prefix[0] = chalk[0]
    for i in range(1, n):
        prefix[i] = prefix[i - 1] + chalk[i]

    k %= prefix[-1]

    return bisect_right(prefix, k)

prefix[0] = chalk[0] starts the prefix sum with the first student's usage.

prefix[i] = prefix[i - 1] + chalk[i] builds the running total so that prefix[i] holds the cumulative chalk used by students 0 through i.

k %= prefix[-1] removes all complete rounds. After this, k only reflects the leftover chalk in the final partial round.

bisect_right(prefix, k) finds the first index where the prefix sum exceeds k. Python's bisect_right returns the insertion point for k in the sorted prefix array, which is exactly the index of the first value strictly greater than k. That student is the one who runs out of chalk.

Notice that bisect_right handles the edge case where k equals a prefix sum value. If k == prefix[i], that means student i used exactly the last piece of chalk. The next student (index i + 1) is the one who has nothing left, and bisect_right correctly returns i + 1.

Complexity analysis

You could also do a linear scan instead of binary search, which keeps the time at O(n) but avoids the import. The binary search version is more interesting because it demonstrates the pattern, and on very large arrays the O(log n) search step matters.

The building blocks

This problem combines two fundamental building blocks:

Prefix sums. The prefix sum array lets you answer "what is the total chalk used by students 0 through i?" in O(1) time per query, after an O(n) build step. This same technique powers problems like Find Pivot Index and range sum queries. Any time you need cumulative totals across a sequence, prefix sums are the tool.

Binary search on a sorted array. The prefix sum array is naturally sorted (all chalk values are positive, so the running total only increases). That means you can binary search it for the boundary between "enough chalk" and "not enough chalk." This is the same binary search you use everywhere, just applied to a derived array instead of the original input.

Edge cases

• k is smaller than chalk[0]: student 0 cannot even use their chalk. The modulo step does not change k, and bisect_right returns 0.
• k is an exact multiple of the total: k % total == 0, which means after complete rounds there is zero chalk left. Student 0 needs chalk but there is none, so the answer is 0. bisect_right(prefix, 0) returns 0, which is correct.
• Single student: chalk = [3], k = 7. After 7 % 3 = 1, student 0 needs 3 but only 1 remains. Answer is 0.
• All students use 1 piece: chalk = [1, 1, 1, 1], k = 10. After 10 % 4 = 2, prefix = [1, 2, 3, 4]. bisect_right([1, 2, 3, 4], 2) returns 2. Student 2 is the answer.

From understanding to recall

The logic behind this solution is clean: skip full rounds with modulo, then binary search the prefix sums. You can follow it right now. But the real test is whether you can reproduce it from scratch in an interview, under pressure, without notes.

That is where spaced repetition helps. You write the prefix sum build, the modulo step, and the bisect_right call from memory. You do it today, again in two days, again in a week. After a few reps, the three-step approach (prefix, modulo, binary search) is locked in. You stop second-guessing whether it should be bisect_left or bisect_right, because you have written it enough times that the choice is automatic.

Related posts

• Binary Search (LeetCode 704) - The foundation for the binary search step used to locate the target student in the prefix array
• Data Structure: Arrays - Core array operations and patterns including prefix sums, the key preprocessing step in this problem
• Sliding Window Pattern - Another technique for efficient array processing that avoids redundant re-computation, sharing the same "precompute to skip work" philosophy