Count Missing Sample Runs
Easy About 15 min Free, no account needed
Count every contiguous interval with no recorded sample, even when the timeline is too large to expand.
The brief
A recorder was expected to capture one sample in each integer slot from 0 through horizon - 1. Its log contains only the slots it successfully recorded, in increasing order.
An analyst can request any nonempty contiguous interval of slots. Count how many different requests would contain no recorded sample. Two intervals are different if their start or end slot differs. Count shorter intervals inside a gap as well as the whole gap.
For recorded = [2, 5] and horizon = 7, return 7. The missing slots are 0, 1, 3, 4, 6, and the qualifying intervals are:
[0, 0] [1, 1] [0, 1]
[3, 3] [4, 4] [3, 4]
[6, 6]For recorded = [] and horizon = 3, return 6: three single-slot intervals, two length-two intervals, and the whole length-three interval.
Implement long Solve(int[] recorded, int horizon).
0 <= horizon <= 2_147_483_647.0 <= recorded.Length <= 300_000.recordedis strictly increasing, contains no duplicates, and every value satisfies0 <= value < horizon.- A zero-length horizon has no intervals and an empty log.
- Return a
long; the number of intervals can exceed the range ofint. - Do not change
recorded.
A sparse log can describe billions of slots. Visiting every slot or enumerating every missing interval takes too long. Aim for O(n) time and O(1) extra space, where n is the number of recorded slots.
Starter code
using System;
public class Solution
{
public long Solve(int[] recorded, int horizon)
{
throw new NotImplementedException();
}
}How it is graded
Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.
What it practices
- Math and number theory
- Replace enumeration with a formula: GCD, modular arithmetic, digit math and closed-form counting.
Related katas
- Add Binary Strings Easy Free Add two binary numbers far too long for any built-in integer.
- Base64 Decoded Length Easy Free The decoded size is pure arithmetic - no need to decode.
- Excel Column Number Easy Free Spreadsheet columns are base-26 with no zero digit.
- GCD of an Array Easy Free The greatest common divisor of many numbers - Euclid, not trial division.