Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1894.html

1894. Find the Student that Will Replace the Chalk

Level

Medium

Description

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.

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^5
  • 1 <= chalk[i] <= 10^5
  • 1 <= k <= 10^9

Solution

Calculate the prefix sums of chalk, and at the same time the sum of all elements in chalk can be calculated. Calculate the remainder of k % sum, where sum is the sum of all elements in chalk. Then loop over the prefix sums and find the first prefix sum that is greater than the remainder, and return the corresponding index.

  • class Solution {
    public int chalkReplacer(int[] chalk, int k) {
        int n = chalk.length;
        long[] prefixSums = new long[n];
        prefixSums[0] = chalk[0];
        for (int i = 1; i < n; i++)
            prefixSums[i] = prefixSums[i - 1] + chalk[i];
        long remainder = ((long) k) % prefixSums[n - 1];
        for (int i = 0; i < n; i++) {
            if (prefixSums[i] > remainder)
                return i;
        }
        return -1;
    }
}

############

class Solution {
    public int chalkReplacer(int[] chalk, int k) {
        int n = chalk.length;
        long[] s = new long[n + 1];
        s[0] = chalk[0];
        for (int i = 1; i < n; ++i) {
            s[i] = s[i - 1] + chalk[i];
        }
        k %= s[n - 1];
        int left = 0, right = n - 1;
        while (left < right) {
            int mid = (left + right) >> 1;
            if (s[mid] > k) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

  • // OJ: https://leetcode.com/problems/find-the-student-that-will-replace-the-chalk/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int chalkReplacer(vector<int>& A, int k) {
        long sum = accumulate(begin(A), end(A), 0L), i = 0, N  = A.size();
        k %= sum;
        while (k >= A[i]) {
            k -= A[i];
            ++i;
        }
        return i;
    }
};

  • class Solution:
    def chalkReplacer(self, chalk: List[int], k: int) -> int:
        s = list(accumulate(chalk))
        k %= s[-1]
        return bisect_right(s, k)

############

# 1894. Find the Student that Will Replace the Chalk
# https://leetcode.com/problems/find-the-student-that-will-replace-the-chalk

class Solution:
    def chalkReplacer(self, chalk: List[int], k: int) -> int:
        n = len(chalk)
        ssum = k % (sum(chalk))

        for i,x in enumerate(chalk):
            if ssum < x: return i
            
            ssum -= x
        
        


  • func chalkReplacer(chalk []int, k int) int {
	n := len(chalk)
	s := make([]int, n+1)
	for i := 0; i < n; i++ {
		s[i+1] = s[i] + chalk[i]
	}
	k %= s[n]
	return sort.Search(n, func(i int) bool { return s[i+1] > k })
}

  • impl Solution {
    pub fn chalk_replacer(chalk: Vec<i32>, k: i32) -> i32 {
        let pre_sum: Vec<i64> = chalk
            .into_iter()
            .map(|x| x as i64)
            .scan(0, |state, x| {
                *state += x;
                Some(*state)
            })
            .collect();

        pre_sum
            .binary_search(&(k as i64 % pre_sum.last().unwrap()))
            .map_or_else(|e| e, |v| v + 1) as i32
    }
}


  • function chalkReplacer(chalk: number[], k: number): number {
    let s = 0;
    for (const x of chalk) {
        s += x;
    }
    k %= s;
    for (let i = 0; ; ++i) {
        if (k < chalk[i]) {
            return i;
        }
        k -= chalk[i];
    }
}

All Problems

All Solutions