2006 Find The Student That Will Replace The Chalk
Find the Student that Will Replace the Chalk 
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 pieces.
Example 1:
1
2
3
4
5
6
7
8
9
10
11
**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:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
**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:
1
2
3
4
chalk.length == n
1 <= n <= 105
1 <= chalk[i] <= 105
1 <= k <= 109
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution:
def chalkReplacer(self, chalk: List[int], k: int) -> int:
if k >= sum(chalk):
k = k % sum(chalk)
pre_sum = [0] * len(chalk)
s = 0
for idx, m in enumerate(chalk):
s += m
pre_sum[idx] = s
start = 0
end = len(chalk) - 1
while(start < end):
mid = int((end + start) / 2)
#print(mid)
if pre_sum[mid] > k and pre_sum[mid-1] <= k:
return mid
if pre_sum[mid] == k:
return mid + 1
if pre_sum[mid] > k:
end = mid-1
if pre_sum[mid] < k:
start = mid+1
return start