Count Distinct Values in a Massive Sorted Array

You are given a very large sorted (non‑decreasing) array arr of length $$n$$. The array may contain billions of elements, but the number of distinct values $$k$$ is known to be quite small – at most a few hundred. Your task is to compute exactly how many unique values appear in arr. A simple linear scan solves the problem and runs in $$O(n)$$ time. However, because $$k \ll n$$, we can do much better. Run‑jumping approach Instead of inspecting every element one by one,…