1894. Find the Student that Will Replace the Chalk
Approach
Sum all chalk; reduce k mod total sum; linear scan to find who runs out.
Key Techniques
Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.
Binary search reduces search space by half each step, giving O(log n) time. Beyond sorted arrays, apply it on the answer space ("binary search on result") when you can define a monotonic predicate — e.g., "can we achieve X with k resources?"
A prefix sum array pre-computes cumulative values so any range query is answered in O(1). The classic sum of range [l, r] = prefix[r+1] - prefix[l]. 2D prefix sums extend this to matrix sub-rectangle queries. Combine with a hash map for "subarray sum equals k" problems.
// Approach: Sum all chalk; reduce k mod total sum; linear scan to find who runs out.
// Time: O(n) Space: O(1)
public class Solution
{
public int ChalkReplacer(int[] chalk, int k)
{
long k1 = k;
long sum = 0;
for (int i = 0; i < chalk.Length; i++)
sum += chalk[i];
k1 %= sum;
if (k1 == 0)
return 0;
for (int i = 0; i < chalk.Length; ++i)
{
k1 -= chalk[i];
if (k1 < 0)
return i;
}
throw new ArgumentException();
}
}