LeetCode 1894 - Find the Student that Will Replace the Chalk

LeetCode Problem 1894

Difficulty: 🟡 Medium
Topics: Array, Binary Search, Simulation, Prefix Sum

Solution

Problem Understanding

The problem presents a classroom scenario where students are given problems in a round-robin order, consuming a certain number of chalk pieces for each problem. We are given an array chalk, where chalk[i] indicates the number of chalk pieces student i uses, and an integer k representing the initial chalk supply. Starting from student 0, each student uses chalk in order, wrapping back to student 0 after student n-1. The goal is to determine which student will first run out of chalk, meaning the current supply is strictly less than what the student requires.

The input consists of an array of length n (1 ≤ n ≤ 10^5) and an integer k (1 ≤ k ≤ 10^9). Each chalk consumption value is between 1 and 10^5. This implies that a brute-force iteration over k chalk uses is infeasible due to potentially enormous values. We must exploit patterns or cumulative sums to optimize.

Important edge cases include situations where k is smaller than the first student's chalk requirement, or when k is extremely large, requiring multiple complete rounds through all students.

Approaches

The brute-force approach simulates the process exactly as described. Starting with student 0, we subtract chalk[i] from k and proceed to the next student. When k is smaller than the current student's chalk requirement, we return that student's index. While correct, this approach is inefficient because in the worst case, we may iterate billions of times when k is large.

The optimal approach relies on the insight that the chalk consumption pattern repeats every n students. We first compute the total chalk used in one full round, total = sum(chalk). If k >= total, we can reduce the problem to k % total because complete rounds do not affect the final outcome. After computing k % total, we iterate through the students once, using cumulative subtraction, until the remaining chalk is insufficient for a student. This reduces the iteration from potentially billions to at most n.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(k)	O(1)	Simulates each student's chalk usage until replacement
Optimal	O(n)	O(1)	Uses modulo to skip full rounds and a single pass to find replacement

Algorithm Walkthrough

1. Compute the sum of all chalk requirements: total = sum(chalk). This represents the chalk used in one complete round of all students.
2. Reduce the remaining chalk to the remainder after full rounds: k = k % total. This works because each full round does not change which student will replace the chalk.
3. Iterate through each student i in order:

• If k < chalk[i], student i cannot complete the problem and must replace the chalk. Return i.
• Otherwise, subtract chalk[i] from k and continue.

4. Since the modulo operation guarantees that the replacement will occur within one pass, the iteration is guaranteed to terminate before the end of the array.

Why it works: The modulo operation preserves the position of the student who will run out of chalk, because any full rounds are irrelevant. The cumulative subtraction ensures the first student who exceeds the remaining chalk is correctly identified.

Python Solution

from typing import List

class Solution:
    def chalkReplacer(self, chalk: List[int], k: int) -> int:
        total = sum(chalk)
        k %= total  # reduce k to the remaining chalk after full rounds
        
        for i, c in enumerate(chalk):
            if k < c:
                return i
            k -= c
        return 0  # fallback, technically unreachable due to constraints

This implementation first calculates the total chalk used in a complete cycle. The modulo operation then reduces the effective chalk count. The loop iterates once through the array, returning the first student whose chalk requirement exceeds the remaining chalk.

Go Solution

func chalkReplacer(chalk []int, k int) int {
    total := 0
    for _, c := range chalk {
        total += c
    }
    
    k %= total
    
    for i, c := range chalk {
        if k < c {
            return i
        }
        k -= c
    }
    return 0
}

The Go solution mirrors the Python approach. We sum the chalk array, reduce k modulo total, and iterate over the students, returning the index where k < chalk[i]. Go's integer arithmetic is sufficient for the input constraints, as total and k are within int range for these limits.

Worked Examples

Example 1: chalk = [5,1,5], k = 22

Student	Chalk	k before	k after
0	5	22	17
1	1	17	16
2	5	16	11
0	5	11	6
1	1	6	5
2	5	5	0
0	5	0	-

Student 0 must replace the chalk.

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

total = 3+4+1+2 = 10 → k % total = 25 % 10 = 5

Student	Chalk	k before	k after
0	3	5	2
1	4	2	-

Student 1 must replace the chalk.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	We sum the array once and iterate through it once at most
Space	O(1)	Only a few variables are used; no additional data structures

The modulo operation ensures that we never perform more than one pass through the array, which makes this solution efficient even for large k.

Test Cases

# Provided examples
assert Solution().chalkReplacer([5,1,5], 22) == 0  # basic scenario with multiple rounds
assert Solution().chalkReplacer([3,4,1,2], 25) == 1  # multiple rounds with modulo reduction

# Edge cases
assert Solution().chalkReplacer([1], 1) == 0  # single student, k equals chalk
assert Solution().chalkReplacer([1], 0) == 0  # single student, k zero
assert Solution().chalkReplacer([2,3,4], 1) == 0  # not enough for first student
assert Solution().chalkReplacer([2,3,4], 9) == 0  # exactly one full round
assert Solution().chalkReplacer([2,3,4], 10) == 0  # just over one full round

Test	Why
[5,1,5], 22	Validates multiple rounds and cumulative subtraction
[3,4,1,2], 25	Tests modulo reduction
[1], 1	Single student edge case
[1], 0	Zero chalk edge case
[2,3,4], 1	Not enough chalk for first student
[2,3,4], 9	Exactly one full round
[2,3,4], 10	Over one full round, replacement occurs at start

Edge Cases

Case 1: Only one student

If there is a single student, they will always replace the chalk when k < chalk[0] or after multiple rounds when k is insufficient. Our implementation correctly handles this by iterating over a single element and checking k < chalk[0].

Case 2: k smaller than the first student's chalk

When k < chalk[0], the first student must immediately replace the chalk. The modulo operation does not change k, so the loop correctly returns index 0.

Case 3: k exactly a multiple of total chalk

If k is exactly equal to sum(chalk) or any multiple, k % total becomes 0. The first student in the iteration then has k < chalk[i] and replaces the chalk, which matches expected behavior. This ensures correctness for edge alignment with full rounds.