Topic describes

This is 1894 on LeetCode. Finding the student number that needs chalk is medium difficulty.

Tag: “prefix and”, “dichotomy”, “simulation”

There are n students in a class, numbered from 0 to N-1. Each student will answer the questions in turn, with student 0 first, then student 1, and so on, until student N-1, and then the teacher will repeat the process, starting with student 0 again.

You are given an array of integers with length N and subscripts starting from 0 chalk and an integer k. I started with k pieces of chalk in my pencil box. When student I answers the question, he will consume chalk[I]. If the amount of chalk left is strictly less than Chalk [I], student I needs to replenish chalk.

Please return the number of the student whose chalk needs replenishing.

Example 1:

Input: chalk = [5,1,5], k = 22 Output: 0 explanation: the students consume chalk as follows: - the student numbered 0 uses 5 pieces of chalk, then k = 17. - Student number 1 uses 1 piece of chalk, and then k = 16. - Student 2 uses 5 pieces of chalk, and then k = 11. - Student 0 uses 5 pieces of chalk, and k = 6. - Student number 1 uses 1 piece of chalk, and then k = 5. - Student number 2 uses 5 pieces of chalk, and then k = 0. Student 0 doesn't have enough chalk, so he needs to replenish it.Copy the code

Example 2:

Input: chalk = [3,4,1,2], k = 25 Output: 1 explanation: students consume chalk as follows: - the student numbered 0 uses 3 pieces of chalk, then k = 22. - Student number 1 uses 4 pieces of chalk, and then k = 18. - Student number 2 uses 1 piece of chalk, and then k = 17. - Student number 3 uses 2 pieces of chalk and then k = 15. - Student 0 uses 3 pieces of chalk, then k = 12. - Student 1 uses 4 pieces of chalk, and then k = 8. - Student 2 uses 1 piece of chalk, and then k = 7. - Student number 3 uses 2 pieces of chalk, and then k = 5. - Student 0 uses 3 pieces of chalk and k = 2. Student 1 doesn't have enough chalk, so he needs to replenish it.Copy the code

Tip:

  • chalk.length == n
  • 1 <= n <=
    1 0 5 10^5
  • 1 <= chalk[i] <=
    1 0 5 10^5
  • 1 <= k <=
    1 0 9 10^9

Prefix and + dichotomy

The amount of chalk consumed by each student is fixed, and all the chalk will be recycled to all the students as tirelessly as the teacher’s instruction.

Therefore, we can preprocess prefix and array sumsumsum, and modulo KKK for the total number of chalk consumed by all students in a cycle (sum[n]sum[n]sum[n]) to obtain the number of chalk before the start of the last round.

Then divide the prefix and the array to find the last student who meets the chalk requirement, and the student number of the next student is the answer.

Code:

class Solution {
    public int chalkReplacer(int[] chalk, int k) {
        int n = chalk.length;
        long[] sum = new long[n + 1];
        for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + chalk[i - 1];
        k = (int)(k % sum[n]);
        int l = 1, r = n;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (sum[mid] <= k) l = mid;
            else r = mid - 1;
        }
        return sum[r] <= k ? r : r - 1; }}Copy the code
  • Time complexity: the complexity of preprocessing prefix sum is O(n)O(n)O(n). The complexity of binary solutions is O(log⁡n)O(\log{n})O(logn). The overall complexity is O(n)O(n)O(n)
  • Space complexity: O(n)O(n)O(n)

simulation

Through solution 1, we find that the upper bound of complexity is O(n)O(n)O(n) O(n)O(n)O of the preprocessing prefix sum, and “modulo operation of the total number of chalk consumed in a single cycle” ensures that the remaining number of chalk will be consumed in a single cycle.

Therefore, the dichotomy of O(log⁡n)O(\log{n})O(logn) is not necessary, and only one last round of traversal simulation is needed for Chalk.

Code:

class Solution {
    public int chalkReplacer(int[] chalk, int k) {
        int n = chalk.length;
        long max = 0;
        for (int i : chalk) max += i;
        k = (int)(k % max);
        for (int i = 0; i < n; i++) {
            k -= chalk[i];
            if (k < 0) return i;
        }
        return -1; // never}}Copy the code
  • Time complexity: O(n)O(n)O(n)
  • Space complexity: O(1)O(1)O(1)

The last

This is the No.1894 of our “Brush through LeetCode” series. The series started on 2021/01/01, and there are 1916 questions on LeetCode by the start date.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.