Подсчет чисел в диапазоне [L, R], имеющих только три установленных бита

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

Примеры:

Input: arr[] = {{11, 19}, {14, 19}}
Output: 4
             2
Explanation: 

1. Query(11, 19): Numbers in the range [11, 19] having three set bits are {11, 13, 14, 19}.
2. Query(14, 19): Numbers in the range [14, 19] having three set bits are {14, 19}.

Input: arr[] = {{1, 10}, {6, 12}}
Output: 1
              2
Explanation: 

1. Query(1, 10): Numbers in the range [1, 10] having three set bits are {7}.
2. Query(6, 12): Numbers in the range [6, 12] having three set bits are {7, 12}.

Подход: Идея решения этой проблемы состоит в том, чтобы выполнить предварительное вычисление и сохранить все числа только с 3 битами, установленными в диапазоне [1, 10 ¹⁸ ] , а затем использовать двоичный поиск, чтобы найти положение нижней границы L и верхней границы R и верните ответ, так как есть разница. Выполните следующие шаги, чтобы решить данную проблему:

• Инициализируйте вектор, скажем, V , чтобы хранить все числа в диапазоне [1, 10 ¹⁸ ] только с тремя установленными битами.
• Перебрать каждую тройку, образованную отношением [0, 63] × [0, 63] × [0, 63], используя переменные i, j , и k и выполните следующие шаги:
  • Если i, j и k различны, то вычислить число с установлены i ^-й , j ^-й и k ^-й биты, и если число меньше 10 ¹⁸ , нажмите число в векторе V .
• Отсортируйте вектор V в порядке возрастания.
• Перейдите массив arr[], используя переменную i, и выполните следующие шаги:
  • Сохраните границы запроса в переменных, скажем, L и R соответственно.
  • Найдите положение нижней границы L и верхней границы R в векторе V .
  • Выведите разницу между позициями верхней границы R и нижней границы L как результат.

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

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