#1894

Medium

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Find the Student that Will Replace the Chalk

Identify the first student who will run out of chalk using a simulation with prefix sums and binary search.

array binary search simulation prefix sum

Problem Statement

There is a classroom of n students numbered from 0 to n - 1. Each student uses a certain amount of chalk to solve a problem, given by an array chalk, and the teacher distributes problems in order starting from student 0 repeatedly until the chalk runs out.

Given an integer k representing the initial number of chalk pieces, return the index of the first student who does not have enough chalk to solve their problem and must replace the chalk. Each student uses chalk[i] pieces when it is their turn, and the process repeats cyclically.

Examples

Example 1

Input: chalk = [5,1,5], k = 22

Output: 0

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

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 == n
1 <= n <= 105
1 <= chalk[i] <= 105
1 <= k <= 109

Solution Approach

Compute total chalk and reduce k

Sum all chalk[i] values to get the total chalk per cycle. Reduce k modulo this sum to focus only on the remaining chalk after full cycles, which simplifies the search for the student who will replace it.

Use prefix sums for cumulative consumption

Create a prefix sum array to store cumulative chalk consumption. This allows checking efficiently which student will exceed the remaining chalk without iterating each step individually.

Binary search over student indices

Perform binary search on the prefix sum array to find the first index where cumulative chalk exceeds remaining k. This applies the pattern of binary search over the valid answer space and avoids linear iteration.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(n)

Time complexity is O(n) to compute prefix sums. Space complexity is O(n) for the prefix sum array. Binary search is O(log n), but prefix sum creation dominates.

What Interviewers Usually Probe

They may ask about optimizing the solution beyond naive simulation to handle large k.
Expect hints towards using prefix sums to quickly compare chalk consumption against k.
They might emphasize binary search over the valid answer space instead of iterating linearly.

Common Pitfalls or Variants

Common pitfalls

Not reducing k modulo the total chalk sum, which causes unnecessary repeated simulation.
Misindexing while building the prefix sum, leading to off-by-one errors in binary search.
Assuming k will always run out exactly at a student's turn instead of strictly less than chalk[i].

Follow-up variants

Return the total number of full cycles completed before the chalk runs out.
Allow dynamic updates to chalk array and find the next student after each update.
Compute the student who runs out first when students can skip turns based on certain rules.

FAQ

How does the binary search pattern apply in Find the Student that Will Replace the Chalk?

Binary search is applied on the prefix sum of chalk consumption to find the first student whose cumulative chalk usage exceeds the remaining k.

Why do we use k modulo total chalk sum?

Reducing k modulo total chalk sum accounts for full cycles and focuses only on the remaining chalk, avoiding unnecessary repeated simulation.

Can we solve this problem without prefix sums?

Yes, but iterating over each student each cycle leads to higher runtime; prefix sums allow efficient cumulative checks.

What happens if k equals the sum of chalk?

After full cycles, k becomes zero, so the first student in the next cycle will need to replace the chalk.

Is this problem limited to integer chalk values?

Yes, all chalk values are integers, and the binary search relies on cumulative integer sums to find the correct student index.

terminal

Solution

Solution 1: Sum and Modulo + Simulation

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.

1

2

3

4

5

6

7

8

class Solution:
    def chalkReplacer(self, chalk: List[int], k: int) -> int:
        s = sum(chalk)
        k %= s
        for i, x in enumerate(chalk):
            if k < x:
                return i
            k -= x

Continue Practicing

#1889 minimum space wasted from packaging #1862 sum of floored pairs #1838 frequency of the most frequent element