Recuento de enteros de la forma (2^x * 3^y) en el rango [L, R]

Dado un rango [L, R] donde 0 ≤ L ≤ R ≤ 10 ⁸ . La tarea es encontrar el conteo de enteros del rango dado que se puede representar como (2 ^x ) * (3 ^y ) .
Ejemplos: 
 

Entrada: L = 1, R = 10 
Salida: 7 
Los números son 1, 2, 3, 4, 6, 8 y 9
Entrada: L = 100, R = 200 
Salida: 5 
Los números son 108, 128, 144, 162 y 192 
 

Enfoque: dado que los números, que son potencias de dos y tres, crecen rápidamente, puede usar el siguiente algoritmo. Para todos los números de la forma (2 ^x ) * (3 ^y ) en el rango [1, 10 ⁸ ] guárdelos en un vector. Luego ordenar el vector. Luego, la respuesta requerida se puede calcular utilizando un límite superior . El cálculo previo de estos números enteros será útil cuando haya varias consultas de la forma [L, R] .
A continuación se muestra la implementación del enfoque anterior:
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
#define MAXI (int)(1e8)
 
// To store all valid integers
vector<int> v;
 
// Function to find all the integers of the
// form (2^x * 3^y) in the range [0, 1000000]
void precompute()
{
 
    // To store powers of 2 and 3
    // initialized to 2^0 and 3^0
    int x = 1, y = 1;
 
    // While current power of 2
    // is within the range
    while (x <= MAXI) {
 
        // While number is within the range
        while (x * y <= MAXI) {
 
            // Add the number to the vector
            v.push_back(x * y);
 
            // Next power of 3
            y *= 3;
        }
 
        // Next power of 2
        x *= 2;
 
        // Reset to 3^0
        y = 1;
    }
 
    // Sort the vector
    sort(v.begin(), v.end());
}
 
// Function to find the count of numbers
// in the range [l, r] which are
// of the form (2^x * 3^y)
void countNum(int l, int r)
{
    cout << upper_bound(v.begin(), v.end(), r)
                - upper_bound(v.begin(), v.end(), l - 1);
}
 
// Driver code
int main()
{
    int l = 100, r = 200;
 
    // Pre-compute all the valid numbers
    precompute();
 
    countNum(l, r);
 
    return 0;
}

# Python3 implementation of the approach
import bisect
MAXI=int(1e8)
 
# To store all valid integers
v=[]
 
# Function to find all the integers of the
# form (2^x * 3^y) in the range [0, 1000000]
def precompute():
 
    # To store powers of 2 and 3
    # initialized to 2^0 and 3^0
    x = 1; y = 1
 
    # While current power of 2
    # is within the range
    while (x <= MAXI) :
 
        # While number is within the range
        while (x * y <= MAXI) :
 
            # Add the number to the vector
            v.append(x * y)
 
            # Next power of 3
            y *= 3
         
 
        # Next power of 2
        x *= 2
 
        # Reset to 3^0
        y = 1
     
 
    # Sort the vector
    v.sort()
 
 
# Function to find the count of numbers
# in the range [l, r] which are
# of the form (2^x * 3^y)
def countNum(l, r):
    print(bisect.bisect_right(v, r) - bisect.bisect_right(v,l - 1))
 
 
# Driver code
if __name__ == '__main__':
    l = 100; r = 200
 
    # Pre-compute all the valid numbers
    precompute()
 
    countNum(l, r)

5

Complejidad de tiempo: O(N * log(N)), donde N = logX + logY
Espacio auxiliar: O(N), ya que se ha tomado N espacio adicional.