Find the Student That Will Replace the Chalk — Solution
Find the Student That Will Replace the Chalk solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Find the Student That Will Replace the Chalk is a medium coding problem on arrays, binary search and prefix sum, asked in Amazon, Google and Paytm interviews.
- Difficulty: Medium
- Topics: Arrays, Binary Search, Prefix Sum, Simulation
- 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 <= 1000001 <= chalk[i] <= 1000001 <= k <= 1000000000
Hints for Find the Student That Will Replace the Chalk
Hint 1
Full rounds are wasted simulation — reduce
kmodulo the round total first.Hint 2
After that reduction, the answer is the first student whose prefix sum exceeds the remainder.
Hint 3
Binary search the prefix sums, or scan them linearly.
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
ktok % total— the leftover at the start of the final partial round. - Binary search the first index
iwithpre[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 thoughkfitsint. - Simulating question by question is
O(k)and times out atk = 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 loJava
public static int chalkReplacer(int[] chalk, int k) {
int n = chalk.length;
long[] pre = new long[n];
long total = 0;
for (int i = 0; i < n; i++) {
total += chalk[i];
pre[i] = total;
}
long rem = k % total;
int lo = 0, hi = n - 1;
while (lo < hi) {
int mid = (lo + hi) >>> 1;
if (pre[mid] > rem) hi = mid; else lo = mid + 1;
}
return lo;
}C++
int chalkReplacer(vector<int>& chalk, int k) {
int n = (int) chalk.size();
vector<long long> pre(n);
long long total = 0;
for (int i = 0; i < n; i++) {
total += chalk[i];
pre[i] = total;
}
long long rem = k % total;
int lo = 0, hi = n - 1;
while (lo < hi) {
int 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Binary Search