Dare2Solve
Given an array chalk
where chalk[i]
represents the amount of chalk that the i-th
student needs to write on the chalkboard, and an integer k
representing the total chalk available, determine the index of the student who will run out of chalk.
The process continues in rounds, starting from the first student and moving sequentially to the next until one student cannot pick up the required chalk amount. This student's index is the output.
The original problem can lead to a time limit exceeded error if k
is significantly large, as the naive solution iterates through the array repeatedly. However, by leveraging the total sum of chalk needed for one full round, we can reduce the problem size. By reducing k
by the total sum modulo operation, we avoid unnecessary full cycles and focus only on the remaining chalk after full rounds.
k
by the total sum: By applying k %= total
, we ensure k
is less than the total sum, thus eliminating unnecessary full rounds.k
until k
becomes less than the chalk required by the current student. The index of this student is the answer.O(n)
, where n
is the number of students. The solution iterates through the array twice—once to compute the total sum and once to determine the student who will run out of chalk.
O(1)
, since we only use a few extra variables regardless of the input size.
class Solution {
public:
int chalkReplacer(vector<int>& chalk, int k) {
long long total = 0;
for (int c : chalk) {
total += c;
}
k %= total;
for (int i = 0; i < chalk.size(); ++i) {
if (chalk[i] > k) {
return i;
}
k -= chalk[i];
}
return -1; // This should never be reached
}
};
class Solution:
def chalkReplacer(self, chalk, k):
total = sum(chalk)
k %= total
for i in range(len(chalk)):
if chalk[i] > k:
return i
k -= chalk[i]
return -1 # This should never be reached
class Solution {
public int chalkReplacer(int[] chalk, int k) {
int i = 0;
while (chalk[i] <= k) {
k -= chalk[i];
i = (i >= chalk.length - 1) ? 0 : i + 1;
}
return i;
}
}
var chalkReplacer = function (chalk, k) {
let i = 0
while (chalk[i] <= k) {
k -= chalk[i]
if (i >= chalk.length - 1) i = 0
else i++
}
return i
};