Проверьте, можно ли уменьшить данный массив до 0, удалив элемент меньше K и добавив его в K

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

Дан массив arr[] размера N и целое число K . Если значение в arr[] меньше или равно K , то это значение будет удалено из массива и добавлено к K . Задача состоит в том, чтобы проверить, все ли элементы в arr[] могут быть поглощены или нет.

Примеры:

Input: K = 10, arr[] = {3, 9, 19, 5, 21}
Output: true
Explanation: The array elements are absorbed in following way.
One way to absorption is {9, 19, 5, 3, 21}
value is 9 and the New k value: 10 + 9 = 19
value is 19 and the New k value: 19 + 19 = 38
value is 5 and the New k value: 38 + 5 = 43
value is 3 and the New k value: 43 + 3 = 46
value is 9 and the New k value: 46 + 21 = 6. 
Hence, All values are absorbed.

Input: K = 5, arr[] = {4, 9, 23, 4}
Output: false

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

  • Любой элемент в arr[] , который с наибольшей вероятностью будет меньше или равен K , будет наименьшим элементом.
  • Итак, отсортируйте массив в порядке неубывания и попробуйте удалить элементы слева направо.
  • Итерируйте слева направо, удаляя значения arr[] .
  • В любой момент, если невозможно удалить какой-либо элемент, вернуть false .
  • В противном случае верните true .

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


Сложность времени: О (N * логN)
Вспомогательное пространство: О(1)

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