Sponsored
Sponsored
This approach takes advantage of the cyclical nature of the problem. Initially, the teacher provides problems to each student in sequence. We calculate the total sum of chalk required for one full pass through the students. If k is greater than this sum, it implies that the whole cycle can be repeated multiple times. Therefore, we reduce k by this sum repeatedly to get only the relevant chalk pieces needed as a remainder, then find the student who will run out of chalk.
Time Complexity: O(n), where n is the number of students since we iterate over the chalk array twice, once to find the total chalk and then to find the replacer.
Space Complexity: O(1) as we use only a constant amount of extra space.
1public class Solution {
2 public int ChalkReplacer(int[] chalk, int k) {
3 long total = 0;
4 foreach (int c in chalk) {
5 total += c;
6 }
7 k %= total;
8 for (int i = 0; i < chalk.Length; i++) {
9 if (k < chalk[i]) return i;
10 k -= chalk[i];
11 }
12 return -1;
13 }
14}Following C# syntax, the implementation first calculates the total amount of chalk in one cycle and reduces k using modulo arithmetic, then identifies the student with insufficient chalk.
This approach accumulates a prefix sum of chalk costs as an extra preprocessing step. With prefix sums, one can quickly determine the range that k falls into using binary search, leading to the index of the student who will run out of chalk.
Time Complexity: O(n log n) due to sorting and binary search.
Space Complexity: O(n) for the prefix sums array.
1using System;
2
public class Solution {
public int ChalkReplacer(int[] chalk, int k) {
int n = chalk.Length;
long[] prefixSum = new long[n];
prefixSum[0] = chalk[0];
for (int i = 1; i < n; i++) {
prefixSum[i] = prefixSum[i - 1] + chalk[i];
}
k %= prefixSum[n - 1];
int lo = 0, hi = n - 1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (prefixSum[mid] > k) hi = mid;
else lo = mid + 1;
}
return lo;
}
}In C#, the prefix sum array is used similarly as in other languages to store pre-calculated summations, allowing quick calculation of the index where chalk runs out using binary search.