1894. Find the Student that Will Replace the Chalk

Problem Description

In this problem, you're given an integer array chalk and an integer k, which represent the number of chalk pieces available for a group of students to use. Each element in the chalk array corresponds to the amount of chalk that each student will use to solve a problem. For example, chalk[0] is the amount of chalk the first student will use, chalk[1] the amount for the second student, and so on, in a repeating cycle.

The sequence starts with the first student (index 0) and goes to the last student (index n - 1). After the teacher has distributed problems to all students, the cycle starts again with the first student. This continues until there aren't enough chalk pieces for a student to use. At that point, the student will be asked to replace the chalk.

The task is to find out which student will be asked to replace the chalk. In other words, you need to return the index of the first student who cannot proceed because the chalk pieces left are fewer than what they need.


To solve this problem, it's efficient to use a prefix sum and binary search.

Prefix Sum: First, we calculate the cumulative chalk usage for each student, which gives us a sequence where each element tells us the total amount of chalk used by all students up to that point. This can be done using the accumulate function from the itertools module in Python, which creates a list of accumulated sums.

Binary Search: Then, because the cycle starts again after reaching the last student, we can take the total amount of chalk k and find the remainder when divided by the total accumulated chalk. This tells us how much chalk would be left after an integer number of full cycles, and the next student to take a problem would need more chalk than what we have. Using this leftover amount of chalk, we can perform a binary search to find the first student who would need more chalk than the remnants. The built-in function bisect_right from the bisect module in Python can help us here. It searches for the place to insert the leftover chalk amount in order to maintain the sorted order. This position, effectively the index of the student, is the output of our function.

Learn more about Binary Search and Prefix Sum patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

What is the worst case running time for finding an element in a binary search tree(not necessarily balanced) of size n?

Solution Approach

The solution approach for this problem is to first calculate the prefix sum of the chalk requirements for each student and then use a binary search algorithm to find the index of the student who will replace the chalk.

Here's a step-by-step breakdown of the implementation described by the provided solution code:

  1. Calculate Prefix Sum: Using the accumulate function from the itertools module, we calculate the cumulative sum of the chalk array. The result is a new list s where s[i] represents the total amount of chalk used by the first i + 1 students. This step is crucial because it allows us to understand the total chalk consumption in one complete cycle through all students.

  2. Modulo Operation: The value of k may be very large, possibly larger than the total amount of chalk used in a full cycle by all students. To handle this, we use the modulo operation k %= s[-1] which gives us the remainder of k after dividing by the total chalk used in one cycle (s[-1] represents the total chalk used after all students have taken a problem once). This effectively reduces the problem to a single incomplete cycle, making it easier to find the student who will replace the chalk.

  3. Binary Search: Now, we need to identify the first student who cannot proceed due to insufficient chalk. This is done by using the bisect_right function from the bisect module, which performs a binary search. The function finds the position where the leftover chalk k would be inserted to maintain the sorted order of the accumulated chalk list s. The returned index bisect_right(s, k) is the index of the first student whose chalk requirement exceeds the amount of leftover chalk k.

Combining these steps, the code successfully determines the student who will replace the chalk:

1class Solution:
2    def chalkReplacer(self, chalk: List[int], k: int) -> int:
3        s = list(accumulate(chalk))  # step 1
4        k %= s[-1]                   # step 2
5        return bisect_right(s, k)    # step 3

Even though this approach appears straightforward, it's highly efficient because both the prefix sum and binary search operate in O(n) and O(log n) time complexities, respectively, making the whole solution quite performant for even large input sizes.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which algorithm should you use to find a node that is close to the root of the tree?

Example Walkthrough

Let's walk through the solution approach with a small example to illustrate how it works in practice. Consider the chalk array [5, 1, 3] and k = 11:

  1. We first calculate the prefix sum, which tells us the cumulative amount of chalk used by the students in one round:

    1Original chalk array: [5, 1, 3]
    2Prefix sum: [5, 6, 9]

    With this, we can see that one full cycle of chalk usage by all students amounts to 9.

  2. Now we apply the modulo operation to k with the total chalk used in one cycle:

    1k = 11
    2Total chalk in one cycle = 9 (from the last element of the prefix sum)
    3k % 9 = 2

    The modulo gives 2, so after completing one full round, we have 2 chalks left.

  3. Using binary search, we find where 2 (the remaining chalk pieces) would be inserted in our prefix sum array to maintain the sorted order:

    1Prefix sum array: [5, 6, 9]
    2Leftover: 2

    A binary search for 2 in the array [5, 6, 9] would place it before the first element since 2 is less than 5. Therefore, it would be inserted at index 0.

Thus, the student at index 0 (the first student) would be the one who can't proceed because they require 5 chalks, and we only have 2 remaining. Hence, the answer is 0, the index of the first student in our chalk array.

Solution Implementation

1# First, we need to import the required functions from the itertools and bisect modules.
2from itertools import accumulate
3from bisect import bisect_right
5class Solution:
6    def chalkReplacer(self, chalk: List[int], k: int) -> int:
7        # Accumulate the chalk requirements in a list
8        # to find out the total chalk needed for one round.
9        total_chalk_per_round = list(accumulate(chalk))
11        # The remaining chalk after multiple complete rounds
12        # is the remainder of k divided by the total chalk per round.
13        k %= total_chalk_per_round[-1]
15        # Find the index of the smallest number in the accumulated
16        # chalk list that is greater than k using binary search.
17        # This is the index of the student who will be the next to receive chalk.
18        return bisect_right(total_chalk_per_round, k)
20# We need to import the typing module to use List[int] as a type hint in the function signature
21from typing import List
1class Solution {
2    public int chalkReplacer(int[] chalk, int k) {
3        int numberOfStudents = chalk.length;
5        // Define a prefix sum array with an extra space for easier calculations
6        long[] prefixSum = new long[numberOfStudents + 1];
8        // Calculate the prefix sum of chalk requirements
9        // Here, starting index of prefixSum should be 1 to match the chalk indices.
10        prefixSum[1] = chalk[0];
11        for (int i = 1; i < numberOfStudents; ++i) {
12            prefixSum[i + 1] = prefixSum[i] + chalk[i];
13        }
15        // Find the remaining chalk after it has been distributed once
16        k %= prefixSum[numberOfStudents];
18        // Initialize search boundaries for binary search
19        int left = 0, right = numberOfStudents;
21        // Performing binary search to find the minimum index 'left'
22        // such that prefixSum[left] is greater than 'k'
23        while (left < right) {
24            int mid = (left + right) >> 1; // Equivalent to (left + right) / 2 but more efficient
26            // If the sum up to mid is greater than k, search the left half
27            if (prefixSum[mid] > k) {
28                right = mid;
29            } else { // Otherwise, search the right half
30                left = mid + 1;
31            }
32        }
34        // The index 'left' points to the first student that cannot finish 
35        // their chalk round, that's the student to start the next round 
36        return left - 1; // Adjusting the index because prefixSum started from 1 instead of 0
37    }
1#include <vector>
2#include <algorithm> // Needed for std::upper_bound
4class Solution {
6    // Function to find the index of the student who will receive the last chalk piece before the chalk runs out
7    int chalkReplacer(vector<int>& chalk, int k) {
8        int numStudents = chalk.size();
9        vector<long long> prefixSum(numStudents, chalk[0]);
10        // Calculate prefix sums of chalk requirements
11        for (int i = 1; i < numStudents; ++i) {
12            prefixSum[i] = prefixSum[i - 1] + chalk[i];
13        }
14        // The amount of chalk K is now how much chalk will be needed in the last round
15        // because we are interested in a full cycle where every student has received chalk exactly once
16        k %= prefixSum[numStudents - 1];
18        // Use upper bound to return the first element in the prefix sum which is greater than k
19        // this will be the first student who will not be able to finish writing as the chalk will run out before this student
20        return std::upper_bound(prefixSum.begin(), prefixSum.end(), k) - prefixSum.begin();
21    }
1// Import the necessary functions from `lodash` for calculating the prefix sums and finding the upper bound.
2import _ from 'lodash';
4// Function to calculate prefix sums of an array.
5const calculatePrefixSums = (chalk: number[]): number[] => {
6  const prefixSums: number[] = [];
7  chalk.reduce((acc, current) => {
8    const sum = acc + current;
9    prefixSums.push(sum);
10    return sum;
11  }, 0);
12  return prefixSums;
15// Main function to find the index of the student who will receive the last chalk piece before the chalk runs out.
16const chalkReplacer = (chalk: number[], k: number): number => {
17  const numStudents = chalk.length;
18  const prefixSums: number[] = calculatePrefixSums(chalk);
19  // Adjust the number of chalk (k) by taking modulus with the total sum to find remainder chalk after full cycles.
20  k %= prefixSums[prefixSums.length - 1];
22  // Use lodash's sortedIndex to find the smallest index at which k should be inserted 
23  // into `prefixSums` in order to maintain the array's sorted order.
24  const studentIndex: number = _.sortedIndex(prefixSums, k);
26  // This index represents the student who cannot finish writing as the chalk runs out before their turn.
27  return studentIndex;
30export { chalkReplacer };
Not Sure What to Study? Take the 2-min Quiz:

Which of these properties could exist for a graph but not a tree?

Time and Space Complexity

Time Complexity

The time complexity of the given code is determined by two main operations: accumulating the chalk array and performing the binary search.

  • The accumulate function computes the prefix sums of the chalk list, which takes O(n) time, where n is the length of chalk.
  • The modulus operation k %= s[-1] is constant time, O(1).
  • bisect_right is a binary search function, which takes O(log n) time to find the insert position for k in the sorted list s.

Combining these complexities, we get O(n + log n) which simplifies to O(n) since O(n) dominates O(log n).

Space Complexity

The space complexity of the code comes from storing the prefix sums in the list s. Since this list has the same length as the input list chalk, the space complexity is O(n).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

Recommended Readings

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

TA 👨‍🏫