Количество совершенных чисел в заданном диапазоне для запросов Q

Дан массив arr[] , состоящий из N пар, где каждая пара представляет собой запрос вида {L, R} , задача состоит в том, чтобы найти количество совершенных чисел в заданном диапазоне для каждого запроса.

Примеры:

Input: arr[][] = {{1, 10}, {10, 20}, {20, 30}}
Output: 1 1 1
Explanation:

1. Query(1, 10): Perfect numbers in the range is only 6.
2. Query(10, 20): There are no perfect numbers in the range.
3. Query(20, 30): The perfect number in the range is only 28.

Input: arr[][] = {{1, 1000}, {1000, 2000}, {2000, 3000}
Output: 3 0 0
Explanation:

1. Query(1, 1000): Perfect numbers in the range are 6, 28, and 496.
2. Query(1000, 2000): There are no perfect numbers in the range.
3. Query(2000, 3000): There are no perfect numbers in the range.

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

Временная сложность: O(N*M*√M)), где M — максимальный размер диапазона.
Вспомогательное пространство: O(1)

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

• Найдите максимальное значение правой границы диапазона путем обхода массива arr[] и сохраните его в переменной, скажем, MAX.
• Инициализируйте массив, скажем, prefix[] размера MAX+1 со значением каждого элемента как 0 , где prefix[i] хранит количество совершенных чисел до i .
• Переберите диапазон [2, MAX], используя переменную i , и выполните следующие действия:
  • Обновите префикс [i] до префикса [i-1] , а затем проверьте, является ли текущее целое число i идеальным числом, а затем увеличьте префикс [i] на 1.
• Пройдите массив arr[] и на каждой итерации выведите количество совершенных чисел в текущем диапазоне, [L, R] как префикс [R] – префикс [L-1].

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

Временная сложность: O(M*√M+ N), где M — самая большая правая граница.
Вспомогательное пространство: O(M)