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

Имея два стека stack1[] и stack2[] размера N и M соответственно и целое число K , задача состоит в том, чтобы подсчитать максимальное количество целых чисел из двух стеков, сумма которых меньше или равна K .

Примеры:

Input: stack1[ ] = { 60, 90, 120 }
stack2[ ] = { 100, 10, 10, 250 }, K = 130
Output: 3
Explanation: Take 3 numbers from stack1 which are 100 and 10 and 10.
Total sum 100 + 10 + 10 = 120 

Input: stack1[ ] = { 60, 90, 120 }
stack2[ ] = { 80, 150, 80, 150 }, K = 740
Output: 7
Explanation: Select all the numbers because the value K is enough.

Подход: Эта проблема не может быть решена с использованием жадного подхода, потому что в жадном подходе на каждом шаге будет выбрано число, имеющее минимальное значение, но согласно этому первый пример не работает. Эту проблему можно решить, используя префиксную сумму и бинарный поиск. вычислить сумму префиксов обоих стеков и теперь выполнить итерацию для каждого возможного значения 1-го стека и взять цель, которая равна (K – stack1[i]), и применить двоичный поиск ко второму стеку, чтобы получить нижнюю границу stack2[] .
Выполните шаги, указанные ниже:

• Возьмите два новых стека: sumA[] и sumB[] .
• Вычислите префикс обоих стеков stack1[] и stack2[] .
• Итерация на первом стеке.
  • Теперь возьмите переменную remValueOfK и сохраните (K – stack1[i]) .
  • Если он меньше 0, продолжайте цикл.
  • В противном случае возьмите нижнюю границу второго стека.
    • Если нижняя граница больше размера второго стека или значение нижней границы больше значения remValueOfK , просто уменьшите значение переменной нижней границы.
• Сохраните максимальное количество выбранных элементов и верните его в качестве окончательного ответа.

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

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