Find the Student that Will Replace the Chalk

class Solution {
public:
    int findStudent(vector<int>& chalk, int k) {
        int count = chalk.size();

        vector<long> cumulativeSum(count);
        cumulativeSum[0] = chalk[0];
        for (int i = 1; i < count; i++) {
            cumulativeSum[i] = cumulativeSum[i - 1] + chalk[i];
        }

        long totalChalk = cumulativeSum[count - 1];
        long remainder = k % totalChalk;

        return locateIndex(cumulativeSum, remainder);
    }

private:
    int locateIndex(vector<long>& sums, long target) {
        int left = 0, right = sums.size() - 1;

        while (left < right) {
            int mid = left + (right - left) / 2;

            if (sums[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return right;
    }
};

In the problem titled "Find the Student that Will Replace the Chalk," the solution in C++ involves determining which student will require more chalk than what remains in a cycle of chalk distribution. Here's a concise breakdown of how this solution is implemented:

• Start by calculating the cumulative sum of chalk needed by each student. This helps in understanding the total amount of chalk used in one complete rotation through all students.
• Calculate the remainder when the total available chalks (k) are divided by the cumulative sum of chalks required by all students. This remainder represents the amount of chalk left after possibly several complete rounds of distribution.
• Use a binary search to quickly find out which student will exceed the remained chalk on the next iteration. The efficient binary search is implemented within the function locateIndex, reducing the time complexity, especially for large inputs.
• The primary function, findStudent, iterates through the cumulative sums and uses the helper function locateIndex to find the correct student in logarithmic time.

This approach is both time-efficient and space-efficient, providing a clear and manageable method for solving the problem with large datasets. The solution beautifully combines cumulative summing, modulo operation, and binary search to find the precise stopping point efficiently.

class Solution {

    public int findStudent(int[] chalk, int k) {
        int len = chalk.length;

        long[] cumulativeSum = new long[len];
        cumulativeSum[0] = chalk[0];
        for (int i = 1; i < len; i++) {
            cumulativeSum[i] = cumulativeSum[i - 1] + chalk[i];
        }

        long totalSum = cumulativeSum[len - 1];
        long remaining = (k % totalSum);

        return searchChalk(cumulativeSum, remaining);
    }

    private int searchChalk(long[] array, long target) {
        int start = 0, end = array.length - 1;

        while (start < end) {
            int mid = start + (end - start) / 2;

            if (array[mid] <= target) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }

        return end;
    }
}

The task involves writing a Java method named findStudent that determines which student will need more chalk to continue after a certain amount is depleted. This function receives an array of integers representing the quantity of chalk each student needs and an integer k, representing a total amount of chalk used before it runs out.

Here's an outline of how the solution works:

• Calculate the cumulative sum of chalk needed by each student, stored in an array called cumulativeSum. This sum helps in understanding the total amount of chalk consumed as the chalk passes from one student to another.
• Determine the total amount of chalk used by all students in one complete round using the last value of cumulativeSum.
• Calculate the remainder of chalk (remaining) after possibly multiple entire cycles of chalk distribution among students, using modulus operation with k.
• Pass this remainder to the method searchChalk, which uses a binary search to efficiently find the student who will run out of chalk with the given remaining chalk.

The searchChalk method accepts an array and a target (remaining chalk). It performs a binary search:

• Initialize start and end pointers for the array.
• Iterate until the segment is narrowed down to one student, continuously halving the search space based on whether the cumulative amount at the mid index is less than or equal to the target.

By the end of this method, the index end points to the student who cannot continue without additional chalk. This index is returned from findStudent, indicating which student will replace the chalk when it runs out according to the given sequence.

class Solution:
    def findStudent(self, students: List[int], total: int) -> int:
        count = len(students)

        cumulative = [0] * count
        cumulative[0] = students[0]
        for idx in range(1, count):
            cumulative[idx] = cumulative[idx - 1] + students[idx]

        total_chalk = cumulative[-1]
        chalk_left = total % total_chalk

        return self._search_index(cumulative, chalk_left)

    def _search_index(self, sequence, target):
        start = 0
        end = len(sequence) - 1

        while start < end:
            mid = start + (end - start) // 2

            if sequence[mid] <= target:
                start = mid + 1
            else:
                end = mid

        return end

This solution aims to determine which student will be the last to use up a piece of chalk before it runs out, given a list of students where each value represents the amount of chalk each student uses during their turn. The implementation is in Python and involves a few distinct steps:

1. The solution uses a Solution class with two methods: findStudent and _search_index.
2. findStudent method accepts two parameters: students, a list of integers representing the chalk consumption of each student, and total, the total number of chalk pieces available.
3. Inside the findStudent method, a cumulative list is constructed to represent the prefix sum of chalk usage up to any given student.
4. The total amount of chalk used in one full round by all students is determined by the last entry in the cumulative list. The chalk left after several complete rounds is computed using modulo operation.
5. The _search_index method is then called to find out the smallest index in the cumulative list where the remaining chalk is less than or equal to the cumulative consumption. This method performs a binary search, which efficiently narrows down the required student.
6. This approach utilizes the cumulative sum and binary search making the solution efficient with time complexity largely dominated by the O(log n) of the search step after an O(n) preparation of the cumulative sums.

All in all, the provided code efficiently finds the student based on optimal usage of chalk via prefix sums and binary search techniques.