Подсчитайте числа из заданного диапазона, которые можно посетить, пройдя любое количество шагов из диапазона [L, R]

Учитывая два целых числа X , Y и диапазон [L, R] , задача состоит в том, чтобы подсчитать количество целых чисел из диапазона X и Y ( включительно ), которые можно посетить за любое количество шагов, начиная с X. На каждом шаге можно увеличить на L до R.

Примеры:

Input: X = 1, Y = 10, L = 4, R = 6
Output: 6
Explanation: A total of six points can be visited between [1, 10]: 
 

1. 1: Starting point
2. 5: 1 -> 5
3. 6: 1 -> 6
4. 7: 1 -> 7
5. 9: 1 -> 5 -> 9
6. 10: 1 -> 5 -> 10

Input: X = 3, Y = 12, L = 2, R = 3
Output: 9

Подход: Из индекса i можно попасть в любое место между [i+L, i+R], также аналогично для каждой точки j в [i+L, i+R] можно перейти в [j+L, j+R]. Для каждого индекса i эти достижимые диапазоны могут быть отмечены с помощью массива разностей. Следуйте инструкциям ниже для подхода.

• Создайте массив, скажем, diff_arr[] большого размера , чтобы отметить диапазоны.
• Инициализируйте переменную, скажем, count = 0, чтобы подсчитать достижимые точки.
• Первоначально сделайте diff_arr[x] = 1 и diff_arr[x+1] = -1 , чтобы пометить начальную точку X как посещенную.
• Итерация от X к Y и для каждого i обновление diff_arr[i] += diff_arr[i-1] и если diff_arr[i] >= 1 , то обновление diff_arr[i+L] = 1 и diff_arr[i + R + 1] = -1 и количество = количество + 1.
• Наконец, верните count .

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

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