Dada una array arr[] de N pares , donde cada elemento de la array denota una consulta de la forma {L, R}, la tarea es encontrar el recuento de números en el rango [L, R] , que tiene solo 3 bits establecidos para cada consulta {L, R}.
Ejemplos:
Entrada: arr[]={{11, 19}, {14, 19}}
Salida: 4
2
Explicación:
- Consulta (11, 19): los números en el rango [11, 19] que tienen tres bits establecidos son {11, 13, 14, 19}.
- Consulta (14, 19): los números en el rango [14, 19] que tienen tres bits establecidos son {14, 19}.
Entrada: arr[]={{1, 10}, {6, 12}}
Salida: 1
2
Explicación:
- Consulta (1, 10): los números en el rango [1, 10] que tienen tres bits establecidos son {7}.
- Consulta (6, 12): los números en el rango [6, 12] que tienen tres bits establecidos son {7, 12}.
Enfoque: la idea para resolver este problema es hacer un cálculo previo y almacenar todos los números con solo 3 bits establecidos en el rango [1, 10 18 ] , y luego usar la búsqueda binaria para encontrar la posición del límite inferior de L y el límite superior de R y devolver la respuesta ya que hay diferencia. Siga los pasos a continuación para resolver el problema dado:
- Inicialice un vector , digamos V , para almacenar todos los números en el rango [1, 10 18 ] con solo tres bits configurados.
- Iterar sobre cada triplete formado por la relación [0, 63] × [0, 63] × [0, 63] usando las variables i, j y k y realizar los siguientes pasos:
- Si i, j y k son distintos, calcule el número con los bits i , j y k establecidos , y si el número es menor que 10 18 , inserte el número en el vector V.
- Ordena el vector V en orden ascendente.
- Recorra el arreglo arr[], usando la variable i, y realice los siguientes pasos:
- Almacene los límites de la consulta en las variables, digamos L y R , respectivamente.
- Encuentre la posición del límite inferior de L y el límite superior de R en el vector V .
- Imprime la diferencia entre las posiciones del límite superior de R y el límite inferior de L , como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to precompute
void precompute(vector<long long>& v)
{
// Iterate over the range [0, 64]
for (long long i = 0; i < 64; i++) {
// Iterate over the range [0, 64]
for (long long j = i + 1; j < 64; j++) {
// Iterate over the range [0, 64]
for (long long k = j + 1; k < 64; k++) {
// Stores the number with set bits
// i, j, and k
long long int x
= (1LL << i) | (1LL << j) | (1LL << k);
// Check if the number is less
// than 1e18
if (x <= 1e18 && x > 0)
v.push_back(x);
}
}
}
// Sort the computed vector
sort(v.begin(), v.end());
}
// Function to count number in the range
// [l, r] having three set bits
long long query(long long l, long long r,
vector<long long>& v)
{
// Find the lowerbound of l in v
auto X = lower_bound(v.begin(), v.end(), l);
// Find the upperbound of l in v
auto Y = upper_bound(v.begin(), v.end(), r);
// Return the difference
// in their positions
return (Y - X);
}
void PerformQuery(vector<pair<long long, long long> > arr,
int N)
{
// Stores all the numbers in the range
// [1, 1e18] having three set bits
vector<long long> V;
// Function call to perform the
// precomputation
precompute(V);
// Iterate through each query
for (auto it : arr) {
long long L = it.first;
long long R = it.second;
// Print the answer
cout << query(L, R, V) << "\n";
}
}
// Driver Code
int main()
{
// Input
vector<pair<long long, long long> > arr
= { { 11, 19 }, { 14, 19 } };
int N = arr.size();
// Function call
PerformQuery(arr, N);
return 0;
}
4 2
Complejidad de tiempo: 3
Publicación traducida automáticamente
Artículo escrito por UtkarshPandey6 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA