Leetcode Daily Question 02/09/2024 - 1894. Find the Student that Will Replace the Chalk

Problem Description:

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.

from typing import List
class Solution:
  def chalkReplacer(self, chalk: List[int], k: int) -> int:
    n = len(chalk)
    chalk_sum = sum(chalk)
   	remainder = k % chalk_sum
    if remainder == 0:
      return 0
    for i in range(n):
      if remainder < chalk[i]:
        return i
      remainder -= chalk[i]

Explanation:

This is a remainder problem. We continuously subtract the total sum of chalks used in each round of questioning until the remainder is less than the total sum.

Then we just go through to find the correct index where the remainder is less than the number of chalks at that position.

That is the position we want.

def chalkReplacer(chalk, k):
  n = len(chalk)
  chalk_sum = sum(chalk)
  
  remainder = k % chalk_sum
  
  if remainder == 0: # Early termination to speed avoid unecessary loops
    return 0
  
  for i in range(n):
    if remainder < chalk[i]:
      return i
    remainder -= chalk[i]

The time complexity is O(n). Worst case is if the index returned is the last index of the array chalk.

The space complexity is O(1). We only have simple variables to store.

The full solution can be found near the top of the page.