Find the Student that Will Replace the Chalk

Problem Description

Given an array of chalk consumption for each student and an initial amount of chalk, identify the index of the student who will run out of chalk first when solving problems in a cyclic manner.

Key Insights

• The teacher gives problems to students in a round-robin fashion.
• Each student uses a specified amount of chalk from the array.
• The process continues until the teacher cannot provide enough chalk to the next student.
• A prefix sum can help determine how much chalk is used in a full cycle.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve this problem, we can use the following approach:

1. Calculate Total Chalk Needed: First, compute the total amount of chalk needed for one complete round through all students.
2. Determine Full Cycles: Use the total chalk to determine how many complete cycles can be performed with the given chalk k.
3. Find the Remaining Chalk: After completing as many complete cycles as possible, find the remaining chalk.
4. Identify the Student: Iterate through the students in a round-robin fashion until the remaining chalk is insufficient for the next student.

This approach ensures we minimize unnecessary iterations while efficiently determining which student will replace the chalk.

Code Solutions