Find the Student that Will Replace the Chalk

Medium

Asked by:

4 views

Topics:

Arrays

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 <= 10⁵
1 <= chalk[i] <= 10⁵
1 <= k <= 10⁹

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the size of the `chalk` array and the value of `k`?
Can the values in the `chalk` array be zero or negative?
If `k` is initially less than the first element in `chalk`, what should I return?
Is `k` guaranteed to be non-negative?
Is it guaranteed that a student will eventually run out of chalk, or can `k` be large enough to allow infinite turns?

Brute Force Solution

Approach

We're figuring out which student will run out of chalk first by simulating the entire chalk distribution process step-by-step. This means we'll go through each student one by one, subtracting the chalk they need until we find the student who can't complete their task.

Here's how the algorithm would work step-by-step:

Start with the first student.
Subtract the amount of chalk that student needs from the total chalk available.
If the total chalk available is now negative, then that first student is the one who will replace the chalk.
If there's still chalk left, move on to the next student.
Subtract the amount of chalk the second student needs from the remaining chalk.
Again, check if the total chalk available is now negative. If it is, the second student will replace the chalk.
Keep doing this for each student, one after another, until you find a student whose chalk requirement makes the total chalk go negative.
The moment the total chalk goes negative, the current student is the answer.

Code Implementation

def find_student_replacing_chalk_brute_force(
    chalk_needed_by_each_student,
    total_chalk_available
):
    number_of_students = len(chalk_needed_by_each_student)

    for student_index in range(number_of_students):
        # Subtract the chalk needed by current student
        total_chalk_available -= \
            chalk_needed_by_each_student[student_index]

        # If total chalk becomes negative, current student
        # is the one who needs to replace
        if total_chalk_available < 0:

            return student_index

    # This should never happen given problem constraints.
    return 0

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the array of chalk requirements once. In each iteration, it subtracts the chalk needed by the current student from the total available chalk and checks if the remaining chalk becomes negative. The number of iterations is directly proportional to the number of students, n. Therefore, the time complexity is O(n).

Space Complexity

O(1) – The algorithm described iterates through students and subtracts chalk, but it doesn't create any additional data structures that scale with the number of students. It uses only a few variables to keep track of the current student and the remaining chalk. The space used by these variables remains constant regardless of the number of students, represented by N. Therefore, the space complexity is O(1).

Optimal Solution

Approach

We want to find the student who will run out of chalk during a repetitive process. Instead of simulating the entire process, we can use math to significantly speed things up. This involves figuring out the total chalk needed for many rounds and using the remainder to determine the final student.

Here's how the algorithm would work step-by-step:

First, calculate the total amount of chalk needed for a complete cycle of all students doing their work.
Next, determine how many full cycles of students can complete their work before the chalk runs out. We figure this out by dividing the total chalk available by the chalk needed for one cycle.
Calculate the remaining chalk after all complete cycles have been done. This is the remainder of the division from the previous step.
Finally, go through the students one by one, subtracting the chalk each student needs from the remaining chalk. The first student that causes the remaining chalk to go negative is the one who runs out of chalk and needs to replace it.

Code Implementation

def find_student_to_replace_chalk(chalk_needed, chalk_available):
    total_chalk_needed_for_cycle = sum(chalk_needed)

    # Optimize by completing full cycles if possible.
    complete_cycles = chalk_available // total_chalk_needed_for_cycle

    remaining_chalk = chalk_available - (complete_cycles * total_chalk_needed_for_cycle)

    for student_index, chalk_required in enumerate(chalk_needed):
        # Subtract each student's chalk usage from remaining.
        remaining_chalk -= chalk_required

        if remaining_chalk < 0:
            # The student that makes chalk negative is the one.
            return student_index

Big(O) Analysis

Time Complexity

O(n) – The algorithm first calculates the sum of the chalk array, which takes O(n) time, where n is the number of students. Then, it iterates through the chalk array again, subtracting each student's chalk requirement from the remaining chalk until the chalk runs out. This second loop also takes at most O(n) time. Therefore, the overall time complexity is dominated by these two linear operations, resulting in O(n) + O(n), which simplifies to O(n).

Space Complexity

O(1) – The algorithm calculates the total chalk needed, the number of full cycles, and the remaining chalk using only a few constant space variables. It iterates through the students, subtracting chalk amounts, but doesn't create any additional data structures dependent on the number of students (N). Therefore, the space used is constant, regardless of the input array size (N) and the chalk amount, resulting in O(1) space complexity.

Edge Cases

Case	How to Handle
Empty chalk array	Return -1 or throw an exception, indicating invalid input.
k is negative	Return -1 or throw an exception, indicating invalid input.
chalk array contains zero values	The algorithm should handle zeros correctly; a student with zero chalk requirement will always pass the turn until k is reduced enough for another student's chalk amount.
Sum of chalk array is less than or equal to k	Reduce k modulo the sum of the chalk array to effectively simulate multiple cycles of chalk usage before finding the student that replaces the chalk.
chalk array contains very large integer values that might cause integer overflow during summation	Use long data type to store the running sum of chalk or k to prevent integer overflow.
k is very large and close to the maximum integer value	Reducing k modulo the sum of the chalk ensures we don't iterate excessively.
chalk array has only one element and k is less than that element	Return index 0 immediately, as the only student will always replace the chalk.
All elements in chalk are equal	The solution will cycle through the array until k is less than one of the values, handled correctly in the iteration logic.

Empty chalk array

How to Handle:

Return -1 or throw an exception, indicating invalid input.

k is negative

How to Handle:

Return -1 or throw an exception, indicating invalid input.

chalk array contains zero values

How to Handle:

The algorithm should handle zeros correctly; a student with zero chalk requirement will always pass the turn until k is reduced enough for another student's chalk amount.

Sum of chalk array is less than or equal to k

How to Handle:

Reduce k modulo the sum of the chalk array to effectively simulate multiple cycles of chalk usage before finding the student that replaces the chalk.

chalk array contains very large integer values that might cause integer overflow during summation

How to Handle:

Use long data type to store the running sum of chalk or k to prevent integer overflow.

k is very large and close to the maximum integer value

How to Handle:

Reducing k modulo the sum of the chalk ensures we don't iterate excessively.

chalk array has only one element and k is less than that element

How to Handle:

Return index 0 immediately, as the only student will always replace the chalk.

All elements in chalk are equal

How to Handle:

The solution will cycle through the array until k is less than one of the values, handled correctly in the iteration logic.