Минимальное количество необходимых вставок, чтобы первые K натуральных чисел можно было получить как сумму подпоследовательности массива

Дан массив arr[] , состоящий из N положительных целых чисел и целого положительного числа K , задача состоит в том, чтобы найти минимальное количество элементов, которые необходимо вставить так, чтобы все числа из диапазона [1, K] могли быть получены как сумма любой подпоследовательности массива.

Примеры:

Input: arr[] = {1, 3, 5}, K = 10
Output: 1
Explanation:
Appending the element {1} to the array modifies the array to {1, 3, 5, 1}. Now the all the sum over the range [1, K] can be obtained as:

1. Sum 1: The elements are {1}.
2. Sum 2: The elements are {1, 1}.
3. Sum 3: The elements are {3}.
4. Sum 4: The elements are {1. 3}.
5. Sum 5: The elements are {1, 3, 1}.
6. Sum 6: The elements are {1, 5}.
7. Sum 7: The elements are {1, 5, 1}.
8. Sum 8: The elements are {3, 5}.
9. Sum 9: The elements are {1, 3, 5}.
10. Sum 10: The elements are {1, 3, 5, 1}.

Input: arr[] = {2, 6, 8, 12, 19}, K = 20
Output: 2

Подход: Данную задачу можно решить, отсортировав массив в порядке возрастания, а затем попытаться сделать значение суммы в диапазоне [1, K], используя тот факт, что если сумма элементов массива X , то все значения в диапазоне [1, X] . В противном случае требуется вставить значение (сумма + 1) как элемент массива. Выполните следующие шаги, чтобы решить проблему:

• Отсортируйте массив arr[] по возрастанию.
• Инициализируйте переменную, скажем, index как 0 , чтобы сохранить индекс элемента массива, и подсчитайте как 0 , чтобы сохранить результирующие добавленные элементы.
• Если значение arr[0] больше 1 , то необходимо добавить 1 , поэтому увеличьте значение счетчика на 1 . В противном случае увеличьте значение индекса на 1 .
• Инициализируйте переменную, скажем, ожидайте как 2 , чтобы сохранить следующее ожидаемое значение в диапазоне от 1 до K , которое будет сформировано из массива arr[] .
• Повторяйте цикл до тех пор, пока значение expect не будет не больше K , и выполните следующие шаги:
  • Если индекс больше, чем равен N , или arr[index] больше, чем значение expect , то увеличьте значение count на 1 и умножьте значение expect на 2.
  • В противном случае увеличьте значение expect на arr[index] и увеличьте значение index на 1 .
• После выполнения вышеуказанных шагов выведите в качестве результата значение count .

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(max(K, N*log N))
Вспомогательное пространство: O(1)