Find the Student that Will Replace the Chalk

MEDIUM

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.

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.

Constraints:

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

Approaches

Checkout 3 different approaches to solve Find the Student that Will Replace the Chalk. Click on different approaches to view the approach and algorithm in detail.

Brute Force Simulation

This approach directly simulates the process described in the problem. We iterate through the students in a cycle, subtracting the chalk used by each student from the total k. The simulation stops when a student does not have enough chalk, and that student's index is returned.

Algorithm

Initialize an index i = 0.
Start a while(true) loop to simulate the process indefinitely.
Inside the loop, check if the remaining chalk k is strictly less than the chalk required by the current student, chalk[i].
If k < chalk[i], this student cannot take their turn and must replace the chalk. Return the student's index i.
If there is enough chalk, subtract chalk[i] from k.
Move to the next student by updating the index: i = (i + 1) % n.

We use a loop that continuously cycles through the student indices from 0 to n-1. An index variable, say i, keeps track of the current student. In each iteration, we check if the remaining chalk k is less than chalk[i]. If it is, student i cannot solve the problem and must replace the chalk, so we return i. Otherwise, we update k by subtracting chalk[i] and move to the next student by updating i to (i + 1) % n. This process continues until the condition k < chalk[i] is met.

class Solution {
    public int chalkReplacer(int[] chalk, int k) {
        int n = chalk.length;
        int i = 0;
        while (true) {
            if (k < chalk[i]) {
                return i;
            }
            k -= chalk[i];
            i = (i + 1) % n;
        }
    }
}

Complexity Analysis

Time Complexity: O(k). The number of iterations is proportional to `k` divided by the average chalk value. In the worst-case scenario where chalk values are small, the loop runs approximately `k` times. Given `k` can be up to `10^9`, this is too slow.Space Complexity: O(1). We only use a few variables to store the index and the remaining chalk, so the space used is constant.

Pros and Cons

Pros:

Very simple to understand and implement as it follows the problem description literally.

Cons:

The time complexity is dependent on the value of k, which can be very large (10^9), leading to a Time Limit Exceeded (TLE) error on most platforms.

Code Solutions

Checking out 3 solutions in different languages for Find the Student that Will Replace the Chalk. Click on different languages to view the code.

class Solution {
public
  int chalkReplacer(int[] chalk, int k) {
    long s = 0;
    for (int x : chalk) {
      s += x;
    }
    k %= s;
    for (int i = 0;; ++i) {
      if (k < chalk[i]) {
        return i;
      }
      k -= chalk[i];
    }
  }
}

Video Solution

Watch the video walkthrough for Find the Student that Will Replace the Chalk

Algorithms:

Binary Search

Patterns:

Prefix Sum

Data Structures:

Array