Skip to content
Katabench
Try free

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:

Text
[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.

Contract

Implement long Solve(int[] recorded, int horizon).

  • 0 <= horizon <= 2_147_483_647.
  • 0 <= recorded.Length <= 300_000.
  • recorded is strictly increasing, contains no duplicates, and every value satisfies 0 <= value < horizon.
  • A zero-length horizon has no intervals and an empty log.
  • Return a long; the number of intervals can exceed the range of int.
  • Do not change recorded.

Performance

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

C#
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.

C# coding challenges →

What it practices

Math and number theory
Replace enumeration with a formula: GCD, modular arithmetic, digit math and closed-form counting.

Related katas