Количество различных сумм, образованных N числами, взятыми из диапазона [L, R]

Даны три целых числа N , L и R . Задача состоит в том, чтобы посчитать различные суммы, образованные с помощью N чисел из диапазона [L, R] , где любое число может быть взято бесконечное количество раз.

Примеры:

Input: N = 2, L = 1, R = 3
Output: 5
Explanation: Generating all distinct combinations of 2 numbers taken from the range [1, 3]
{1, 1} => sum = 2
{1, 2} => sum = 3
{1, 3} => sum = 4
{2, 2} => sum = 4
{2, 3} => sum = 5
{3, 3} => sum = 6
Therefore, there are 5 (2, 3, 4, 5, 6) different sums possible with 2 numbers taken from range [1, 3].

Input: N = 3, L = 1, R = 9
Output: 10

Наивный подход: самый простой подход к решению данной проблемы — сгенерировать все возможные комбинации N чисел из диапазона [L, R] и затем подсчитайте общие различные суммы, образованные этими комбинациями.

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

Эффективный подход: данная проблема может быть решена путем некоторого наблюдения и использования некоторой математики. Здесь минимальное и максимальное число, которое можно использовать, равно L и R соответственно. Таким образом, минимальная и максимальная возможные суммы, которые могут быть сформированы, равны L*N (все N чисел равны L) и R*N (все N чисел равны R) соответственно. Точно так же могут быть сформированы все другие суммы между этим диапазоном. Выполните следующие шаги, чтобы решить данную проблему.

• Инициализируйте переменную, скажем, minSum = L*N , чтобы сохранить минимально возможную сумму.
• Инициализируйте переменную, скажем, maxSum = R*N , чтобы сохранить максимально возможную сумму.
• Окончательный ответ — это общее число в диапазоне [minSum, maxSum] , т. е . (maxSum — minSum + 1) .

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

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