Максимизируйте X так, чтобы сумма чисел в диапазоне [1, X] была не больше K

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

Примеры:

Input: N = 5, K = 10
Output: 4
Explanation: 
The integers 1, 2, 3, and 4 satisfy the condition.

1. The sum of natural numbers up to integer 1 is equal to 1. Which is less than 10.
2. The sum of natural numbers up to integer 2 is equal to (1+2 =) 3. Which is less than 10.
3. The sum of natural numbers up to integer 3 is equal to (1+2+3 =) 6. Which is less than 10.
4. The sum of natural numbers up to integer 4 is equal to (1+2+3+4 =) 10. Which is equal to 10.

Input: N=3, K=0
Output: 0

Подход: Самый простой подход — пройтись по диапазону [1, N] и подсчитать количество элементов, сумма которых меньше или равна K.

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

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

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

• Инициализируйте переменную, скажем, res как 0 , чтобы сохранить результат.
• Кроме того, инициализируйте две переменные, скажем, low и high , как 1 и N соответственно.
• Повторяйте до тех пор, пока низкий уровень не станет меньше или равен высокому , и выполните следующие шаги:
  • Найдите среднее значение диапазона [low, high] и сохраните его в переменной, скажем, mid .
  • Вычислите сумму натуральных чисел до середины и сохраните ее в переменной, скажем, sum .
  • Если сумма меньше или равна K , обновите res до max(res, mid) и назначьте mid+1 на low .
  • В противном случае назначьте mid-1 на high .
• Наконец, после выполнения вышеуказанных шагов выведите значение res в качестве ответа.

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

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