Find the Student That Will Replace the Chalk — Medium Problem & Solution

Students sit in a row and are asked questions in order 0, 1, …, n-1, 0, 1, … forever. Student i uses chalk[i] pieces of chalk per question.

Difficulty: Medium
Topics: Arrays, Binary Search, Simulation, Prefix Sum
Asked at: Amazon, Google, Paytm
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Students sit in a row and are asked questions in order 0, 1, …, n-1, 0, 1, … forever. Student i uses chalk[i] pieces of chalk per question.

The class starts with k pieces. Return the index of the student who is asked a question when there is not enough chalk left for them.

Example 1

Input: chalk = [5,1,5], k = 22
Output: 0
Explanation: Two full rounds use 22, so student 0 is short on the next question.

Example 2

Input: chalk = [3,4,1,2], k = 25
Output: 1
Explanation: Two full rounds use 20, leaving 5 — student 0 takes 3, then student 1 needs 4.

Example 3

Input: chalk = [1], k = 1000000000
Output: 0

Constraints

1 <= chalk.length <= 100000
1 <= chalk[i] <= 100000
1 <= k <= 1000000000

How to solve Find the Student That Will Replace the Chalk

The chalk use is periodic, so all but the last partial round can be removed with one modulo. What remains is a prefix-sum boundary: the first student whose cumulative use exceeds the leftover chalk is the one who runs out.

Approach

Sum the array to get the round total and build prefix sums.
Reduce k to k % total — the leftover at the start of the final partial round.
Binary search the first index i with pre[i] > rem.

Why it works

After the modulo, rem < total, so some prefix must exceed it and the boundary exists. Student i can answer exactly when pre[i] <= rem — the chalk consumed up to and including them still fits — so the first index failing that test is the one who must replace the chalk.

Complexity

Time — O(n) to build the prefix sums, O(log n) to locate the student
Space — O(n), or O(1) by scanning instead

Pitfalls

The round total reaches 10^5 · 10^5 = 10^10, so it needs 64-bit even though k fits int.
Simulating question by question is O(k) and times out at k = 10^9.
The comparison is pre[i] > rem, strictly — a student who uses exactly the remaining chalk does answer.

Reference solution

Python

from typing import List

def chalkReplacer(chalk: List[int], k: int) -> int:
    n = len(chalk)
    pre = []
    total = 0
    for c in chalk:
        total += c
        pre.append(total)
    rem = k % total
    lo, hi = 0, n - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if pre[mid] > rem:
            hi = mid
        else:
            lo = mid + 1
    return lo

JavaScript

var chalkReplacer = function(chalk, k) {
    var n = chalk.length;
    var pre = [], total = 0, i;
    for (i = 0; i < n; i++) { total += chalk[i]; pre.push(total); }
    var rem = k % total;
    var lo = 0, hi = n - 1;
    while (lo < hi) {
        var mid = (lo + hi) >> 1;
        if (pre[mid] > rem) hi = mid; else lo = mid + 1;
    }
    return lo;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue