Минимальное количество элементов, которые должны быть вставлены в массив для формирования всех значений в [1, K] с использованием суммы подмножества

Опубликовано: 22 Сентября, 2022

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

Примеры:

Input: arr[] = {1, 3}, K = 6
Output: 1
Explanation:
Adding the number 2 to the array modifies the array arr[] to {1, 2, 3}. Now, every sum value  over the range [1, 6] can be formed:

  1. Sum = 1: The subset is {1}.
  2. Sum = 2: The subset is {2}.
  3. Sum = 3: The subset is {3}.
  4. Sum = 4: The subset is {1, 3}.
  5. Sum = 5: The subset is {2, 3}.
  6. Sum = 6: The subset is {1, 2, 3}.

Therefore, the minimum number of elements to be added is 1.

Input: arr[] = {1, 5, 10}, K = 20
Output: 2

Подход: данная проблема может быть решена с использованием жадного подхода, основанного на следующих наблюдениях:

  1. Рассмотрим X как максимальное число, такое что все числа в диапазоне [1, X] могут быть образованы суммированием любого подмножества массива.
  2. Затем можно заметить, что при добавлении целого числа Y к массиву диапазон изменяется на [1, X+Y] , так как теперь можно сформировать каждое число в диапазоне [X, X+Y] .
  3. Поэтому идея состоит в том, чтобы жадно добавить элемент, который больше всего увеличит диапазон и не пропустит ни одного числа в новом полученном диапазоне. Это можно сделать, каждый раз добавляя X к массиву и изменяя X на 2*X.

Выполните следующие шаги, чтобы решить проблему:

  • Инициализируйте две целочисленные переменные, скажем, i и count as 0 , для хранения индекса элементов массива и количества необходимых элементов соответственно.
  • Инициализируйте переменную, скажем, requiredNum как 1 , чтобы хранить числа, до которых может быть сформировано каждое число.
  • Итерируйте, пока requiredNum ≤ K, и выполните следующие операции:
    • Если i < N и requiredNum >= arr[i] , тогда увеличьте requiredNum на arr[i] и i на 1 .
    • В противном случае увеличьте requiredNum на requiredNum и подсчитайте на 1 .
  • Наконец, после выполнения вышеуказанных шагов выведите полученный ответ в count .

Ниже приведена реализация вышеуказанного подхода:

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

РЕКОМЕНДУЕМЫЕ СТАТЬИ