Задача. K-й пропущенный элемент

Дан целочисленный массив nums, который отсортирован по возрастанию и все его элементы уникальны. Также дано целое число k.

Верните k-е недостающее число.

Примеры

1. nums = [4,7,9,10], k = 1
   Output: 5
2. nums = [4,7,9,10], k = 3
   Output: 8 (5,6,7,8,...)

Разбор

Алгоритм тут будет эмпирический, т.е. решение методом проб и ошибок. Начнем с базового случая:

1. Если в массиве всего 1 элемент, тогда мы просто к элементу массиву прибавляем заданное число k и возвращаем результат.
2. В противном случае, проходим по массиву и вычисляем количество пропущенных элементов между текущими соседними элементами массива (nums[i], nums[i - 1]).
3. Если количество пропущенных элементов больше (или равно) заданного числа K, то мы сразу возвращаем значение (nums[i - 1] + K). То есть искомое число находится в промежутке между nums[i - 1] и nums[i].
4. Если количество пропущенных элементов меньше заданного числа K, то вычитаем это число из K и переходим к следующему элементу массива.
5. Если же мы прошли весь массив и искомое число еще не найдено, то оно лежит за пределами последнего элемента массива. Тогда ответом будет значение nums[len - 1] + K.

Реализация

Play-test

https://dotnetfiddle.net/uqIMtV