Find the Student that Will Replace the Chalk

Find the Student that Will Replace the Chalk - Problem

There are n students in a class numbered from 0 to n - 1. The teacher will give each student a problem starting with student number 0, then student number 1, and so on until reaching student number n - 1. After that, the teacher will restart the process, starting with student number 0 again.

You are given a 0-indexed integer array chalk and an integer k. There are initially k pieces of chalk. When student number i is given a problem to solve, they will use chalk[i] pieces of chalk to solve that problem. However, if the current number of chalk pieces is strictly less than chalk[i], then student number i will be asked to replace the chalk.

Return the index of the student that will replace the chalk pieces.

Input & Output

Example 1 — Basic Case

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

› Output: 0

💡 Note: Students use chalk in cycles: Round 1: 5+1+5=11 (k=22→11), Round 2: 5+1+5=11 (k=11→0). In Round 3, student 0 needs 5 chalk but only 0 remains, so student 0 replaces chalk.

Example 2 — Replace in Middle

$ Input: chalk = [3,4,1,2], k = 25

› Output: 1

💡 Note: Total per round = 10. After k%10 = 5 remaining: Student 0 uses 3 (remaining=2), Student 1 needs 4 but only 2 available, so student 1 replaces chalk.

Example 3 — Exact Match

$ Input: chalk = [1,1,1], k = 3

› Output: 0

💡 Note: One complete round uses exactly 3 chalk. After that, k=0 and student 0 needs 1 chalk but none available, so student 0 replaces.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input

Array of chalk needed per student, total chalk k

Process

Students take chalk in cycles until insufficient chalk remains

Output

Index of student who needs to replace chalk

Key Takeaway

🎯 Key Insight: Use modular arithmetic to skip complete cycles and only simulate the final partial round

Asked in

a Amazon 15 G Google 8 M Microsoft 5

The key insight is that we can skip complete cycles of chalk distribution using modular arithmetic. Instead of simulating every single chalk distribution (which would be too slow), we calculate the total chalk needed for one complete round and use k % total to find the remaining chalk after all complete rounds. Then we only need to simulate the final partial round. Best approach is Prefix Sum + Modulo with Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Binary Search on Prefix Sum	O(n + log n)	O(n)	Build prefix sum array and use binary search to find the student
Simulation Approach	O(k)	O(1)	Simulate the entire process by giving chalk to each student one by one
Prefix Sum + Modular Arithmetic	O(n)	O(1)	Calculate total chalk needed for one round, use modulo to skip full rounds

Binary Search on Prefix Sum — Algorithm Steps

Build prefix sum array
Take k modulo total sum
Binary search on prefix array to find first element > k
Return that index

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Prefix

Create cumulative sum array

Apply Modulo

Reduce k using total sum

Binary Search

Find first prefix sum > remaining k

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* chalk, int chalkSize, int k) {
    long long* prefix = (long long*)malloc(chalkSize * sizeof(long long));
    prefix[0] = chalk[0];
    
    for (int i = 1; i < chalkSize; i++) {
        prefix[i] = prefix[i-1] + chalk[i];
    }
    
    k = k % prefix[chalkSize-1];
    
    // Binary search for first element > k
    int left = 0, right = chalkSize - 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (prefix[mid] <= k) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    
    free(prefix);
    return left;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int chalk[1000];
    int chalkSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        chalk[chalkSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int k;
    scanf("%d", &k);
    
    int result = solution(chalk, chalkSize, k);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n + log n)

O(n) to build prefix sum, O(log n) for binary search

⚡ Linearithmic

Space Complexity

O(n)

Prefix sum array stores cumulative sums

⚡ Linearithmic Space

32.0K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Binary Search on Prefix Sum — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler