1894. Find the Student that Will Replace the Chalk

Description

Given an array chalk where chalk[i] represents the amount of chalk that the i-th student needs to write on the chalkboard, and an integer k representing the total chalk available, determine the index of the student who will run out of chalk.

The process continues in rounds, starting from the first student and moving sequentially to the next until one student cannot pick up the required chalk amount. This student's index is the output.

Intuition

The original problem can lead to a time limit exceeded error if k is significantly large, as the naive solution iterates through the array repeatedly. However, by leveraging the total sum of chalk needed for one full round, we can reduce the problem size. By reducing k by the total sum modulo operation, we avoid unnecessary full cycles and focus only on the remaining chalk after full rounds.

Approach

1. Calculate the total sum of chalk needed for one full round: This step sums up all elements in the chalk array.
2. Reduce k by the total sum: By applying k %= total, we ensure k is less than the total sum, thus eliminating unnecessary full rounds.
3. Identify the student who will run out of chalk: Iterate through the chalk array, subtracting each student's chalk requirement from k until k becomes less than the chalk required by the current student. The index of this student is the answer.

Complexity

Time Complexity:

O(n), where n is the number of students. The solution iterates through the array twice—once to compute the total sum and once to determine the student who will run out of chalk.

Space Complexity:

O(1), since we only use a few extra variables regardless of the input size.

Code

C++

class Solution {
public:
    int chalkReplacer(vector& chalk, int k) {
        long long total = 0;
        for (int c : chalk) {
            total += c;
        }

        k %= total;

        for (int i = 0; i < chalk.size(); ++i) {
            if (chalk[i] > k) {
                return i;
            }
            k -= chalk[i];
        }

        return -1; // This should never be reached
    }
};

Python

class Solution:
    def chalkReplacer(self, chalk, k):
        total = sum(chalk)
        k %= total
        
        for i in range(len(chalk)):
            if chalk[i] > k:
                return i
            k -= chalk[i]
        
        return -1  # This should never be reached

Java

class Solution {
    public int chalkReplacer(int[] chalk, int k) {
        int i = 0;
        while (chalk[i] <= k) {
            k -= chalk[i];
            i = (i >= chalk.length - 1) ? 0 : i + 1;
        }
        return i;
    }
}

JavaScript

var chalkReplacer = function (chalk, k) {

    let i = 0
    while (chalk[i] <= k) {
        k -= chalk[i]

        if (i >= chalk.length - 1) i = 0
        else i++
    }
    return i
};