Formatted question description: https://leetcode.ca/all/1894.html

1894. Find the Student that Will Replace the Chalk

Level

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.

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^5
  • 1 <= chalk[i] <= 10^5
  • 1 <= k <= 10^9

Solution

Calculate the prefix sums of chalk, and at the same time the sum of all elements in chalk can be calculated. Calculate the remainder of k % sum, where sum is the sum of all elements in chalk. Then loop over the prefix sums and find the first prefix sum that is greater than the remainder, and return the corresponding index.

class Solution {
    public int chalkReplacer(int[] chalk, int k) {
        int n = chalk.length;
        long[] prefixSums = new long[n];
        prefixSums[0] = chalk[0];
        for (int i = 1; i < n; i++)
            prefixSums[i] = prefixSums[i - 1] + chalk[i];
        long remainder = ((long) k) % prefixSums[n - 1];
        for (int i = 0; i < n; i++) {
            if (prefixSums[i] > remainder)
                return i;
        }
        return -1;
    }
}

All Problems

All Solutions