Количество чисел в диапазоне [L, R], которые можно представить в виде суммы двух совершенных степеней

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

Примеры:

Input: L = 0, R = 1
Output: 2
Explanation:
The valid numbers are:

1. 1 as it can be expressed as, 1 = 1² + 0².
2. 0 as it can be expressed as, 0 = 0² + 0².

Therefore, the count of such numbers is 2.

Input: L = 5, R = 8
Output: 2
Explanation:
The valid numbers are:

1. 5 as it can be expressed as, 5 = 1² + 2².
2. 8 as it can be expressed as, 0 = 0² + 2³.

Therefore, the count of such numbers is 2.

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

• Сгенерируйте всю возможную степень всех чисел, которые меньше R , из 2 и сохраните эти числа в массиве pow[] .
• Инициализируйте логический массив, скажем, arr[] размера (R + 1) как 0 .
• Сгенерируйте все возможные различные пары массива pow[] и, если сумма пар не превышает R , пометьте ее как 1 в массиве arr[] .
• Теперь найдите сумму префиксов массива arr[] .
• После выполнения вышеуказанных шагов выведите в качестве результата значение arr[R] – arr[L – 1] .

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

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