Problem

There are n students in a class numbered from 0 to n - 1. The teacher will give each student a problem starting with the student number 0, then the student number 1, and so on until the teacher reaches the student number n - 1. After that, the teacher will restart the process, starting with the 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 the 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 the student number i will be asked to replace the chalk.

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

Examples

Example 1:

Input: chalk = [5,1,5], k = 22
Output: 0
Explanation: The students go in turns as follows:
- Student number 0 uses 5 chalk, so k = 17.
- Student number 1 uses 1 chalk, so k = 16.
- Student number 2 uses 5 chalk, so k = 11.
- Student number 0 uses 5 chalk, so k = 6.
- Student number 1 uses 1 chalk, so k = 5.
- Student number 2 uses 5 chalk, so k = 0.
Student number 0 does not have enough chalk, so they will have to replace it.

Example 2:

Input: chalk = [3,4,1,2], k = 25
Output: 1
Explanation: The students go in turns as follows:
- Student number 0 uses 3 chalk so k = 22.
- Student number 1 uses 4 chalk so k = 18.
- Student number 2 uses 1 chalk so k = 17.
- Student number 3 uses 2 chalk so k = 15.
- Student number 0 uses 3 chalk so k = 12.
- Student number 1 uses 4 chalk so k = 8.
- Student number 2 uses 1 chalk so k = 7.
- Student number 3 uses 2 chalk so k = 5.
- Student number 0 uses 3 chalk so k = 2.
Student number 1 does not have enough chalk, so they will have to replace it.

Solution

Method 1 - Using summation and modulo operator

Here’s the detailed solution:

  1. Calculate the Total Chalk Usage: Sum the amount of chalk each student needs in one full round.
  2. Reduce the Initial Chalk: Use the modulo operation to find the remaining chalk after distributing it across multiple full rounds.
  3. Find the Student: Iterate through the chalk list and subtract the chalk usage for each student from the remaining chalk until it’s less than what the current student needs. The index at this stage will be the student who needs to replace the chalk.

Video Explanation

Here is the short video explanation:

Code

Java
public class Solution {
    public int chalkReplacer(int[] chalk, int k) {
        // Calculate total chalk usage in one round
        long totalUsage = 0;
        for (int usage : chalk) {
            totalUsage += usage;
        }

        // Determine remaining chalk after full rounds
        long remainingChalk = k % totalUsage;

        // Find the student who will take the last piece of chalk
        for (int i = 0; i < chalk.length; i++) {
            if (remainingChalk < chalk[i]) {
                return i;
            }
            remainingChalk -= chalk[i];
        }

        // This return statement should technically never be reached
        // since the loop should always return within the given constraints.
        return -1;
    }

}
Python
from typing import List


class Solution:
    def chalkReplacer(self, chalk: List[int], k: int) -> int:
        # Calculate total chalk usage in one round
        total_usage = sum(chalk)

        # Determine remaining chalk after full rounds
        remaining_chalk = k % total_usage

        # Find the student who will take the last piece of chalk
        for i, usage in enumerate(chalk):
            if remaining_chalk < usage:
                return i
            remaining_chalk -= usage

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)