Максимальное и минимальное количество элементов с суммой не более K

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

Примеры:

Input: N = 4, arr[ ] = {6, 2, 1, 3}, K = 7
Output: 3 1
Explanation:
Maximum number of elements whose sum is less than equal to K is 3 i.e [1, 2, 3] 
Minimum number of elements whose sum is less than equal to K is 1 i.e [6]

Input: N = 5, arr[] = {6, 2, 11, 3, 20}, K = 50
Output: 5 5

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

• Отсортируйте массив arr[].
• Инициализируйте переменные maxNumEle и minNumEle как 0 , чтобы сохранить минимальное и максимальное количество элементов, сумма которых меньше, чем равна K .
• Инициализируйте переменную cumSum1 для хранения совокупной суммы массива arr[].
• Итерация в диапазоне [0, N-1] с использованием переменной i:
  • Добавить текущий элемент в cumSum1 .
  • Если cumSum1 меньше, чем равно K, то увеличивается на 1 в maxNumEle . В противном случае цикл прерывается.
• Инициализируйте переменную cumSum2 для хранения совокупной суммы массива arr[] .
• Итерация в диапазоне [N-1, 0], используя переменную i :
  • Добавить текущий элемент в cumSum2 .
  • Если cumSum2 меньше, чем равно K , то увеличьте на 1 в minNumEle, в противном случае разорвите цикл.
• После выполнения вышеуказанных шагов выведите maxNumEle и minNumEle в качестве ответа .

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

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