# Find the Student that Will Replace the Chalk
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-the-student-that-will-replace-the-chalk)
Canonical: https://scaleengineer.com/dsa/problems/find-the-student-that-will-replace-the-chalk
**Patterns:** [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array
---
## Problem
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 <= 105`
* `1 <= chalk[i] <= 105`
* `1 <= k <= 109`

# Approaches
## 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.
**Time:** 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:** O(1). We only use a few variables to store the index and the remaining chalk, so the space used is constant.
**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.
### Explanation
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.

```java
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;
        }
    }
}
```
### 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`.

## Prefix Sum with Binary Search
The brute-force approach is slow because it simulates every single step, even for full rounds of students. We can optimize this by first calculating how much chalk is used in one full round. Then, we can use the modulo operator to find the remaining chalk `k` for the final, incomplete round. To find the student in this final round, instead of a linear scan, we can use binary search on a pre-computed prefix sum array.
**Time:** O(n). It takes `O(n)` to build the prefix sum array and `O(log n)` for the binary search. The total complexity is dominated by the prefix sum calculation. · **Space:** O(n). We need an additional array of size `n` to store the prefix sums.
**Pros:** Efficient time complexity, a significant improvement over the brute-force approach for large `k`.; The search part is very fast (`O(log n)`).
**Cons:** Requires extra space proportional to the number of students to store the prefix sum array.
### Explanation
This method avoids the slow, step-by-step simulation for large `k`. We first compute a prefix sum array for `chalk`. `prefixChalk[i]` will hold the total chalk needed for students `0` through `i`. The total sum for a full cycle is `prefixChalk[n-1]`. We can skip all full cycles by taking `k = k % prefixChalk[n-1]`. Now, `k` represents the chalk available for the final round. We need to find the first student `i` whose cumulative chalk requirement, `prefixChalk[i]`, exceeds this remaining `k`. Since the `prefixChalk` array is sorted (monotonically increasing), we can use binary search to find this student index in `O(log n)` time.

```java
class Solution {
    public int chalkReplacer(int[] chalk, int k) {
        int n = chalk.length;
        long[] prefixChalk = new long[n];
        prefixChalk[0] = chalk[0];
        for (int i = 1; i < n; i++) {
            prefixChalk[i] = prefixChalk[i - 1] + chalk[i];
        }

        long totalChalk = prefixChalk[n - 1];
        k %= totalChalk;

        // Binary search to find the student
        int left = 0, right = n - 1;
        int ans = 0;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (prefixChalk[mid] > k) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
}
```
### Algorithm
*   First, create a prefix sum array, `prefixChalk`. `prefixChalk[i]` will store the sum of chalk from index `0` to `i`. Note that the sum can exceed the capacity of a 32-bit integer, so a 64-bit integer type (`long`) must be used.
*   The total chalk for one full round is `prefixChalk[n-1]`.
*   Reduce `k` to find the chalk remaining for the final, incomplete round: `k = k % totalChalk`.
*   The problem now is to find the smallest index `i` such that `prefixChalk[i] > k`.
*   Use binary search on the `prefixChalk` array to find this index `i` efficiently.
*   Return the found index.

## Single Pass Simulation with Sum
This approach is the most efficient. Like the prefix sum method, it starts by calculating the total chalk consumed in one full cycle and uses the modulo operator to find the chalk remaining for the final, incomplete cycle. However, instead of building a prefix sum array and using binary search, it simply performs a single linear scan through the students for this final cycle. This achieves the same optimal time complexity while using constant extra space.
**Time:** O(n). We iterate through the `chalk` array twice in the worst case: once to calculate the sum and once more to find the student in the final round. This results in a linear time complexity. · **Space:** O(1). We only use a single variable to store the total sum, not requiring any additional data structures that scale with the input size.
**Pros:** Optimal time complexity of `O(n)`.; Optimal space complexity of `O(1)`.; Simple to implement and understand.
**Cons:** There are no significant cons to this approach as it is optimal in both time and space.
### Explanation
The key insight is that we only care about the final, incomplete round. We can find the state at the beginning of this round efficiently. First, we iterate through the `chalk` array once to compute the total chalk needed for one full cycle, `totalChalk`. It's important to use a `long` for this sum to avoid overflow. Then, we update `k` to `k % totalChalk`. This new `k` is the amount of chalk left for the final round. Finally, we iterate through the `chalk` array again. For each student `i`, we check if they have enough chalk (`k >= chalk[i]`). If not, we've found our answer: `i`. If they do, we subtract the chalk they use (`k -= chalk[i]`) and proceed to the next student. The first student to not have enough chalk is the answer.

```java
class Solution {
    public int chalkReplacer(int[] chalk, int k) {
        int n = chalk.length;
        long totalChalk = 0;
        for (int c : chalk) {
            totalChalk += c;
        }

        k %= totalChalk;

        for (int i = 0; i < n; i++) {
            if (k < chalk[i]) {
                return i;
            }
            k -= chalk[i];
        }
        
        // This line is theoretically unreachable given the problem constraints
        return -1; 
    }
}
```
### Algorithm
*   Calculate the total sum of chalk required for one full round of students. Use a 64-bit integer (`long`) for the sum to prevent overflow.
*   Reduce `k` by taking the modulo of the total sum: `k %= totalSum`. This gives the amount of chalk available at the start of the final round.
*   Iterate through the students from index `0` to `n-1` one last time.
*   For each student `i`, check if the remaining `k` is less than `chalk[i]`.
*   If it is, student `i` is the one to replace the chalk. Return `i`.
*   Otherwise, subtract `chalk[i]` from `k` and continue to the next student.

# Solutions
### Java

```java
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];
    }
  }
}

```

### CPP

```cpp
class Solution {
public:
  int chalkReplacer(vector<int> &chalk, int k) {
    long long s = accumulate(chalk.begin(), chalk.end(), 0LL);
    k %= s;
    for (int i = 0;; ++i) {
      if (k < chalk[i]) {
        return i;
      }
      k -= chalk[i];
    }
  }
};

```

### Python

```python
class Solution:
    def chalkReplacer(self, chalk: List[int], k: int) -> int: s = sum(chalk) k %= s for i, x in enumerate(chalk): if k < x: return i k -= x

```