UniLecs #Task. Find Kth missing number

Задача: дан массив чисел arr, отсортированный в строго возрастающем порядке, а также целое число K.

Необходимо вывести K-е целое число, которое отсутствует в этом массиве.

Входные данные:

• arr — массив натуральных чисел от 1 до 10⁵. Значения массива — натуральные числа от 1 до 10⁵.
• K — натуральное число от 1 до 10⁵.
• arr[i] < arr[j], где 1 <= i < j <= arr.Length.

Вывод: K-е число, которое отсутствует в исходном массиве.

Примеры:

• arr = [2, 3, 4, 7, 11], K = 5
  Output: 9 (пропущенные числа [1, 5, 6, 8, 9, 10, 12, 13, 14, …], нам нужно взять 5й элемент из пропущенных, то есть число 9).
• arr = [1, 2, 3, 4], k = 2
  Output: 6 (пропущенные числа [5, 6, 7, 8, …], берем 2й элемент из пропущенных, то есть число 6).

Разбор

Здесь есть несколько вариантов решений, одним из самых оптимальных будет использование бинарного поиска с нектр условиями для этой задачи.

Мы же приведем более простой вариант с использованием структуры данных HashSet.

Алгоритм:

1. Все значения массива мы занесем в HashSet для более оптимального поиска элемента в массиве. Сложность операции HashSet.Contains() является близким к O(1), тогда как Array.Contains() равна O(N).
2. Далее в цикле от 1 до (arr.Length + K) мы проверяем элементы, которые пропущены в исходном массиве.
   Примечание: так как в задаче есть граничные значения для массива и для K, то проверяем (arr.Length + K), оно не должно превышать лимит.
3. Как только мы нашли Kй пропущенный элемент, выводим его.

Реализация

C#

https://gist.github.com/unilecs/3edfbcda4ea5db7b22810cea5a920131

Play-test

https://dotnetfiddle.net/A0yNXw