Problem Description

You have a class with n students numbered from 0 to n - 1. The teacher gives problems to students in order: first to student 0, then student 1, and so on until student n - 1. After reaching the last student, the teacher starts over from student 0 again, continuing this cycle.

You're given an array chalk where chalk[i] represents the number of chalk pieces student i needs to solve their problem. You're also given an integer k representing the initial number of chalk pieces available.

The process works as follows:

• Students take turns solving problems in numerical order (0, 1, 2, ..., n-1, 0, 1, 2, ...)
• When it's student i's turn, they need chalk[i] pieces of chalk
• If there are enough chalk pieces (current chalk count ≥ chalk[i]), the student uses chalk[i] pieces and the next student gets their turn
• If there aren't enough chalk pieces (current chalk count < chalk[i]), that student must replace the chalk

Your task is to find which student (return their index) will be the first one who needs to replace the chalk.

For example, if chalk = [5, 1, 5] and k = 22:

• Round 1: Student 0 uses 5 (17 left), Student 1 uses 1 (16 left), Student 2 uses 5 (11 left)
• Round 2: Student 0 uses 5 (6 left), Student 1 uses 1 (5 left), Student 2 uses 5 (0 left)
• Round 3: Student 0 needs 5 but only 0 are left, so student 0 must replace the chalk

The solution uses the fact that students answer in cycles. By finding the total chalk needed for one complete round (sum(chalk)), we can use modulo operation to skip complete rounds and only simulate the final partial round where someone will need to replace the chalk.

Intuition

The key insight is recognizing that the students solve problems in a repeating cycle. If we have 3 students who need [5, 1, 5] pieces of chalk respectively, then each complete round uses exactly 5 + 1 + 5 = 11 pieces of chalk.

Instead of simulating every single student's turn (which could take a very long time if k is large), we can be clever about it. If we have k = 100 pieces of chalk and each round uses 11 pieces, we know we can complete 100 // 11 = 9 full rounds, using up 99 pieces of chalk, leaving us with just 1 piece.

This is where the modulo operation comes in handy. By calculating k % sum(chalk), we directly get the remaining chalk after all complete rounds. In our example, 100 % 11 = 1, which tells us that after all complete rounds, we have 1 piece of chalk left.

Now we only need to simulate one final partial round with this remaining chalk. We go through the students in order:

• If the current student needs more chalk than what's available, they're the one who needs to replace it
• Otherwise, we subtract their chalk usage from the remaining amount and move to the next student

This approach transforms what could be a problem requiring millions of iterations (if k is very large) into a problem that requires at most n iterations after the modulo operation. The time complexity becomes O(n) instead of potentially O(k), which is a massive improvement when k is much larger than n.

Learn more about Binary Search and Prefix Sum patterns.

Solution Approach

The implementation follows a two-phase approach: optimization through modulo operation, followed by simulation.

Phase 1: Optimize with Modulo

First, we calculate the total chalk needed for one complete round:

s = sum(chalk)

Then we reduce k to only the remainder after all complete rounds:

k %= s

This step is crucial for efficiency. If k = 1,000,000 and s = 100, instead of simulating 10,000 complete rounds, we immediately know that after 10,000 rounds we have 0 chalk remaining (1,000,000 % 100 = 0).

Phase 2: Simulate the Final Round

Now we iterate through the students one by one with the remaining chalk:

for i, x in enumerate(chalk):
    if k < x:
        return i
    k -= x

In each iteration:

• i is the current student's index
• x is the amount of chalk student i needs (chalk[i])
• We check if the remaining chalk k is less than what the student needs x
• If k < x, this student cannot solve their problem and must replace the chalk, so we return their index i
• Otherwise, the student uses x pieces of chalk, so we subtract it from k and continue to the next student

The algorithm guarantees to find an answer within this loop because after the modulo operation, k < s, meaning we don't have enough chalk for another complete round. Therefore, some student in this final round must be the one to replace the chalk.

Time Complexity: O(n) where n is the number of students - we iterate through the array at most twice (once for sum, once for simulation)

Space Complexity: O(1) - we only use a constant amount of extra space

Example Walkthrough

Let's walk through a concrete example with chalk = [3, 4, 1, 2] and k = 25.

Step 1: Calculate total chalk for one complete round

• Sum of chalk needed: 3 + 4 + 1 + 2 = 10
• One complete round uses 10 pieces of chalk

Step 2: Use modulo to skip complete rounds

• We can complete 25 // 10 = 2 full rounds
• These 2 rounds use 2 × 10 = 20 pieces of chalk
• Remaining chalk: 25 % 10 = 5

Step 3: Simulate the final partial round with 5 pieces of chalk

• Student 0 needs 3 pieces: 5 >= 3 ✓ (can solve, 2 pieces left)
• Student 1 needs 4 pieces: 2 < 4 ✗ (cannot solve)
• Student 1 must replace the chalk

Let's trace through the actual rounds to verify:

• Round 1: 0 uses 3 (22 left), 1 uses 4 (18 left), 2 uses 1 (17 left), 3 uses 2 (15 left)
• Round 2: 0 uses 3 (12 left), 1 uses 4 (8 left), 2 uses 1 (7 left), 3 uses 2 (5 left)
• Round 3: 0 uses 3 (2 left), 1 needs 4 but only 2 available → Student 1 replaces

The answer is student index 1, which matches our optimized calculation!

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the number of students (length of the chalk array). This is because:

• Computing the sum of the chalk array takes O(n) time
• The modulo operation k %= s takes O(1) time
• In the worst case, the for loop iterates through all n elements of the chalk array

The space complexity is O(1). The algorithm only uses a constant amount of extra space:

• Variable s to store the sum
• Variable i for the loop index
• Variable x for the current chalk value
• No additional data structures are created that scale with input size

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Integer Overflow When Calculating Sum

The Pitfall: When calculating sum(chalk), the total can exceed the integer limits in some programming languages. For instance, if the array has many large values, the sum might overflow. While Python handles arbitrary precision integers automatically, this is a critical issue in languages like Java or C++.

Example Scenario:

chalk = [1000000000, 1000000000, 1000000000]  # Sum = 3,000,000,000

In Java, this sum would overflow a 32-bit integer.

Solution:

• In Python: No action needed as it handles large integers automatically
• In other languages: Use appropriate data types (e.g., long in Java/C++)

// Java example
long totalChalk = 0;
for (int c : chalk) {
    totalChalk += c;
}

2. Forgetting the Modulo Operation Optimization

The Pitfall: Attempting to simulate the entire process without using the modulo operation would result in Time Limit Exceeded (TLE) for large values of k.

Example Scenario:

chalk = [1, 1, 1]
k = 1000000000

Without optimization, you'd simulate 333,333,333+ iterations.

Solution: Always use k %= sum(chalk) before the simulation phase to skip complete rounds.

3. Incorrect Loop Termination

The Pitfall: Some might assume they need to handle the case where the loop completes without returning, adding unnecessary code like:

for i, x in enumerate(chalk):
    if k < x:
        return i
    k -= x
return 0  # Unnecessary - this line will never execute

Why It's Wrong: After k %= sum(chalk), we're guaranteed that k < sum(chalk). This means we cannot complete another full round, so someone must run out of chalk.

Solution: Trust the mathematical guarantee - no need for additional return statements after the loop.

4. Off-by-One Error in Understanding the Problem

The Pitfall: Misunderstanding when to return the student index - returning the student who just used the last pieces of chalk instead of the one who needs to replace it.

Example:

# Wrong approach
for i, x in enumerate(chalk):
    k -= x
    if k <= 0:  # Wrong condition
        return i

This returns the student who might have exactly used up all chalk, not the one who needs to replace it.

Solution: Check if there's enough chalk BEFORE the student uses it:

# Correct approach
for i, x in enumerate(chalk):
    if k < x:  # Check first
        return i
    k -= x  # Then deduct