1894. Find the Student that Will Replace the Chalk

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

Approach 01:

#include <vector>
#include <numeric> // For std::accumulate

using namespace std;

class Solution {
    public:
    int chalkReplacer(vector<int>& chalk, int chalkSupply) {
        // Calculate the total chalk needed for one full round
        chalkSupply %= accumulate(chalk.begin(), chalk.end(), 0L);
        
        // If no chalk is left after the full round, return the first student
        if (chalkSupply == 0){
            return 0;
        }        

        // Iterate through the chalk array to find the student who will run out of chalk
        for (int studentIndex = 0; studentIndex < chalk.size(); ++studentIndex) {
            chalkSupply -= chalk[studentIndex];
            if (chalkSupply < 0){
                return studentIndex;
            }
        }

        throw;  // This line will not be reached, just a safeguard
    }
};

from typing import List

class Solution:
    def chalkReplacer(self, chalk: List[int], chalkSupply: int) -> int:
        # Calculate the total chalk needed for one full round
        chalkSupply %= sum(chalk)
        
        # If no chalk is left after the full round, return the first student
        if chalkSupply == 0:
            return 0

        # Iterate through the chalk list to find the student who will run out of chalk
        for studentIndex in range(len(chalk)):
            chalkSupply -= chalk[studentIndex]
            if chalkSupply < 0:
                return studentIndex

        raise Exception("This line will not be reached")  # Safeguard

01. Time Complexity

• Step 1: Calculating the Total Chalk Needed for One Full Round

  The total chalk needed for one full round is calculated using the std::accumulate function. This operation has a time complexity of \( O(n) \), where n is the number of students in the chalk array.

• Step 2: Iterating Through the Chalk Array

  In the worst-case scenario, we may need to iterate through the entire chalk array to find the student who will run out of chalk. This step also has a time complexity of \( O(n) \).

• Overall Time Complexity

  The overall time complexity is \( O(n) \), since both the accumulation and the iteration steps are linear in terms of the number of students.

02. Space Complexity

• Auxiliary Space

  The algorithm uses a constant amount of extra space for variables like chalkSupply and studentIndex. The std::accumulate function also does not require additional space beyond these variables. Therefore, the space complexity is \( O(1) \).

• Overall Space Complexity

  The overall space complexity is \( O(1) \) because the algorithm only requires a fixed amount of extra space regardless of the input size.