{"id":8552,"date":"2021-08-09T19:44:29","date_gmt":"2021-08-10T02:44:29","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8552"},"modified":"2021-08-09T19:45:17","modified_gmt":"2021-08-10T02:45:17","slug":"leetcode-1894-find-the-student-that-will-replace-the-chalk","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/math\/leetcode-1894-find-the-student-that-will-replace-the-chalk\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1894. Find the Student that Will Replace the Chalk"},"content":{"rendered":"\n

There are n<\/code> students in a class numbered from 0<\/code> to n - 1<\/code>. The teacher will give each student a problem starting with the student number 0<\/code>, then the student number 1<\/code>, and so on until the teacher reaches the student number n - 1<\/code>. After that, the teacher will restart the process, starting with the student number 0<\/code> again.<\/p>\n\n\n\n

You are given a 0-indexed<\/strong> integer array chalk<\/code> and an integer k<\/code>. There are initially k<\/code> pieces of chalk. When the student number i<\/code> is given a problem to solve, they will use chalk[i]<\/code> pieces of chalk to solve that problem. However, if the current number of chalk pieces is strictly less<\/strong> than chalk[i]<\/code>, then the student number i<\/code> will be asked to replace<\/strong> the chalk.<\/p>\n\n\n\n

Return the index<\/strong> of the student that will replace<\/strong> the chalk<\/em>.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

Input:<\/strong> chalk = [5,1,5], k = 22\nOutput:<\/strong> 0\nExplanation: <\/strong>The students go in turns as follows:\n- Student number 0 uses 5 chalk, so k = 17.\n- Student number 1 uses 1 chalk, so k = 16.\n- Student number 2 uses 5 chalk, so k = 11.\n- Student number 0 uses 5 chalk, so k = 6.\n- Student number 1 uses 1 chalk, so k = 5.\n- Student number 2 uses 5 chalk, so k = 0.\nStudent number 0 does not have enough chalk, so they will have to replace it.<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> chalk = [3,4,1,2], k = 25\nOutput:<\/strong> 1\nExplanation: <\/strong>The students go in turns as follows:\n- Student number 0 uses 3 chalk so k = 22.\n- Student number 1 uses 4 chalk so k = 18.\n- Student number 2 uses 1 chalk so k = 17.\n- Student number 3 uses 2 chalk so k = 15.\n- Student number 0 uses 3 chalk so k = 12.\n- Student number 1 uses 4 chalk so k = 8.\n- Student number 2 uses 1 chalk so k = 7.\n- Student number 3 uses 2 chalk so k = 5.\n- Student number 0 uses 3 chalk so k = 2.\nStudent number 1 does not have enough chalk, so they will have to replace it.\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • chalk.length == n<\/code><\/li>
  • 1 <= n <= 105<\/sup><\/code><\/li>
  • 1 <= chalk[i] <= 105<\/sup><\/code><\/li>
  • 1 <= k <= 109<\/sup><\/code><\/li><\/ul>\n\n\n\n
    Solution: Math<\/strong><\/h2>\n\n\n\n
    Sum up all the students. k %= sum to skip all the middle rounds.<\/p>\n\n\n\n
    Time complexity: O(n)
    Space complexity: O(1)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int chalkReplacer(vector& chalk, int k) {    \n    long sum = accumulate(begin(chalk), end(chalk), 0L);\n    k %= sum;\n    for (size_t i = 0; i < chalk.size(); ++i)\n      if ((k -= chalk[i]) < 0) return i;\n    return -1;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    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…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[49],"tags":[31,177,158],"class_list":["post-8552","post","type-post","status-publish","format-standard","hentry","category-math","tag-math","tag-medium","tag-mod","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8552","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=8552"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8552\/revisions"}],"predecessor-version":[{"id":8554,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8552\/revisions\/8554"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8552"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8552"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8552"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}