Problem Description

You are given an array chalk where chalk[i] represents the number of chalk pieces the i-th student uses to solve a problem. There are n students in a classroom, and they answer questions in a round-robin fashion (i.e., when the last student finishes, the first student goes again).

You are also given an integer k representing the total number of chalk pieces available. Starting with the first student (index 0), each student uses chalk[i] pieces in turn. If a student needs more chalk than is left, they cannot proceed, and that student will replace the chalk. Your goal is to return the index of the student who will replace the chalk.

• Each student uses their required amount of chalk in order.
• Once the chalk runs out (i.e., k is less than the chalk needed for the next student), return that student's index.
• There is always exactly one valid answer.
• Each element in chalk is a positive integer.
• Do not reuse chalk or skip students.

Thought Process

To solve this problem, let's first think about the straightforward approach: we can simulate each student using chalk one by one, subtracting their chalk usage from k until we don't have enough chalk left for the next student. When this happens, we return that student's index.

However, this can be inefficient if k is very large, since we might loop through the students many times. To optimize, we notice that the process is cyclic: once all students have taken a turn, we start again from the first student. So, instead of simulating every single chalk usage, we can calculate how many full rounds we can complete with the given chalk, and then focus only on the remaining chalk.

This shift from brute-force simulation to a more mathematical approach (using modulo operation) is key to making the solution efficient.

Solution Approach

Here is the step-by-step approach:

1. Compute the total chalk needed for one full round:
   • Sum all elements in chalk to get the total chalk needed for all students to take one turn each.
2. Reduce k using modulo:
   • Since the process is cyclic, we can compute k % total to find out how much chalk remains after as many full rounds as possible.
3. Find the student who will replace the chalk:
   • Iterate through the chalk array, subtracting each student's chalk usage from k (now reduced).
   • When k is less than the chalk needed for a student, return that student's index.

This approach is efficient because we avoid unnecessary iterations and only loop through the students at most twice: once to sum, and once to find the answer.

Example Walkthrough

Let's use the input chalk = [5, 1, 5] and k = 22.

1. Sum the chalk array:
   total = 5 + 1 + 5 = 11
2. Reduce k:
   k = 22 % 11 = 0
3. Find the student:
   • Student 0 needs 5 chalk. k = 0 is less than 5.
   • So, student 0 will replace the chalk.

The answer is 0.

Time and Space Complexity

Brute-force approach:

• Time Complexity: O(k) in the worst case (very slow if k is large).
• Space Complexity: O(1) (no extra data structures needed).

• Time Complexity: O(n), where n is the number of students (once to sum, once to find the answer).
• Space Complexity: O(1), since only a few variables are used.

The optimized approach is much faster, especially when k is very large.

Summary

In summary, the key insight is recognizing the cyclic nature of the problem. By using the modulo operation, we can avoid simulating every single chalk usage and instead focus on the remainder after full rounds. This makes our solution efficient and elegant, reducing time complexity from potentially O(k) to O(n), and making it suitable for large inputs.

Code Implementation

class Solution:
    def chalkReplacer(self, chalk, k):
        total = sum(chalk)
        k = k % total
        for i, c in enumerate(chalk):
            if k < c:
                return i
            k -= c

class Solution {
public:
    int chalkReplacer(vector<int>& chalk, int k) {
        long long total = 0;
        for (int c : chalk) total += c;
        k = k % total;
        for (int i = 0; i < chalk.size(); ++i) {
            if (k < chalk[i]) return i;
            k -= chalk[i];
        }
        return -1; // This line should never be reached
    }
};

class Solution {
    public int chalkReplacer(int[] chalk, int k) {
        long total = 0;
        for (int c : chalk) total += c;
        k = (int)(k % total);
        for (int i = 0; i < chalk.length; i++) {
            if (k < chalk[i]) return i;
            k -= chalk[i];
        }
        return -1; // Should never reach here
    }
}

var chalkReplacer = function(chalk, k) {
    let total = chalk.reduce((a, b) => a + b, 0);
    k = k % total;
    for (let i = 0; i < chalk.length; i++) {
        if (k < chalk[i]) return i;
        k -= chalk[i];
    }
};