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.

#1894

Medium

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

找到需要补充粉笔的学生编号

一个班级里有 n 个学生，编号为 0 到 n - 1 。每个学生会依次回答问题，编号为 0 的学生先回答，然后是编号为 1 的学生，以此类推，直到编号为 n - 1 的学生，然后老师会重复这个过程，重新从编号为 0 的学生开始回答问题。给你一个长度为 n 且下标从 0 开始的整数数组 chalk …

数组二分查找模拟前缀和

题目描述

一个班级里有 n 个学生，编号为 0 到 n - 1 。每个学生会依次回答问题，编号为 0 的学生先回答，然后是编号为 1 的学生，以此类推，直到编号为 n - 1 的学生，然后老师会重复这个过程，重新从编号为 0 的学生开始回答问题。

给你一个长度为 n 且下标从 0 开始的整数数组 chalk 和一个整数 k 。一开始粉笔盒里总共有 k 支粉笔。当编号为 i 的学生回答问题时，他会消耗 chalk[i] 支粉笔。如果剩余粉笔数量 严格小于 chalk[i] ，那么学生 i 需要补充粉笔。

请你返回需要补充粉笔的学生编号。

示例 1：

输入：chalk = [5,1,5], k = 22
输出：0
解释：学生消耗粉笔情况如下：
- 编号为 0 的学生使用 5 支粉笔，然后 k = 17 。
- 编号为 1 的学生使用 1 支粉笔，然后 k = 16 。
- 编号为 2 的学生使用 5 支粉笔，然后 k = 11 。
- 编号为 0 的学生使用 5 支粉笔，然后 k = 6 。
- 编号为 1 的学生使用 1 支粉笔，然后 k = 5 。
- 编号为 2 的学生使用 5 支粉笔，然后 k = 0 。
编号为 0 的学生没有足够的粉笔，所以他需要补充粉笔。

示例 2：

输入：chalk = [3,4,1,2], k = 25
输出：1
解释：学生消耗粉笔情况如下：
- 编号为 0 的学生使用 3 支粉笔，然后 k = 22 。
- 编号为 1 的学生使用 4 支粉笔，然后 k = 18 。
- 编号为 2 的学生使用 1 支粉笔，然后 k = 17 。
- 编号为 3 的学生使用 2 支粉笔，然后 k = 15 。
- 编号为 0 的学生使用 3 支粉笔，然后 k = 12 。
- 编号为 1 的学生使用 4 支粉笔，然后 k = 8 。
- 编号为 2 的学生使用 1 支粉笔，然后 k = 7 。
- 编号为 3 的学生使用 2 支粉笔，然后 k = 5 。
- 编号为 0 的学生使用 3 支粉笔，然后 k = 2 。
编号为 1 的学生没有足够的粉笔，所以他需要补充粉笔。

提示：

chalk.length == n
1 <= n <= 10⁵
1 <= chalk[i] <= 10⁵
1 <= k <= 10⁹

lightbulb

解题思路

方法一：求和取余 + 模拟

由于学生的回答是一轮一轮循环进行的，因此我们可以将所有学生需要消耗的粉笔数加起来，得到一个总数 $s$ 。然后我们对 $k$ 取 $s$ 的余数，即可知道最后一轮结束后剩余的粉笔数。

接下来，我们只需要模拟最后一轮即可。初始时，剩余的粉笔数为 $k$ ，编号为 $0$ 的学生开始回答问题。当剩余的粉笔数小于当前学生需要的粉笔数时，当前学生需要补充粉笔，我们直接返回当前学生的编号 $i$ 即可。否则，我们将剩余的粉笔数减去当前学生需要的粉笔数，并将当前学生的编号 $i$ 加一，进行下一次模拟。

时间复杂度 $O(n)$ ，其中 $n$ 是学生的数量。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

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

speed

复杂度分析

指标	值
时间	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.
空间	O(n)

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#1889 装包裹的最小浪费空间 #1862 向下取整数对和 #1838 最高频元素的频数