Find the Student That Will Replace the Chalk
Problem
Students 0..n−1 in a circle consume chalk[i] units of chalk on their turn. With k units of chalk, who will be next to need a replacement?
chalk = [5,1,5], k = 220def chalk_replacer(chalk, k):
s = sum(chalk)
k %= s
for i, c in enumerate(chalk):
if k < c: return i
k -= c
return -1 # unreachablefunction chalkReplacer(chalk, k) {
let s = 0;
for (const c of chalk) s += c;
k %= s;
for (let i = 0; i < chalk.length; i++) {
if (k < chalk[i]) return i;
k -= chalk[i];
}
return -1;
}class Solution {
public int chalkReplacer(int[] chalk, int k) {
long s = 0;
for (int c : chalk) s += c;
long rem = k % s;
for (int i = 0; i < chalk.length; i++) {
if (rem < chalk[i]) return i;
rem -= chalk[i];
}
return -1;
}
}int chalkReplacer(vector<int>& chalk, int k) {
long s = 0;
for (int c : chalk) s += c;
long rem = k % s;
for (int i = 0; i < (int)chalk.size(); i++) {
if (rem < chalk[i]) return i;
rem -= chalk[i];
}
return -1;
}Explanation
Students sit in a circle using chalk repeatedly, so the pattern just repeats every full round. The trick is to skip all the complete rounds at once with the modulo operator instead of simulating them.
One full round uses s = sum(chalk) units. So k %= s instantly throws away every complete loop, leaving only the chalk used in the final partial round.
Now we walk the students once from index 0. For each student, if the remaining chalk k is less than what they need (chalk[i]), they are the one who must replace it, so we return i. Otherwise we subtract their usage and continue.
Example: chalk = [5,1,5], k = 22. The sum is 11, and 22 % 11 = 0. Student 0 needs 5 but only 0 is left, so the answer is 0.
The modulo handles potentially huge k in one step, and the final scan is a single pass, giving O(n) time.