Dadas las consultas Q, cada consulta consta de dos números enteros L y R, la tarea es encontrar los números totales entre L y R (ambos inclusive), que tienen casi tres bits establecidos en su representación binaria.
Ejemplos :
Input : Q = 2
L = 3, R = 7
L = 10, R = 16
Output : 5
6
For the first query, valid numbers are 3, 4, 5, 6, and 7.
For the second query, valid numbers are 10, 11, 12, 13, 14 and 16.
Requisitos previos : manipulación de bits y búsqueda binaria
Método 1 (simple) : un enfoque ingenuo es recorrer todos los números entre L y R y encontrar el número de bits establecidos en cada uno de esos números. Incrementa una variable de contador si un número no tiene más de 3 bits establecidos. Devuelve la respuesta como contador. Nota : Este enfoque es muy ineficiente ya que los números L y R pueden tener valores grandes (hasta 10 18 ).
Método 2 (Eficiente) : Un enfoque eficiente requerido aquí es el precálculo. Dado que los valores de L y R se encuentran dentro del rango [0, 10 18] (ambos inclusive), por lo que su representación binaria puede tener como máximo 60 bits. Ahora, dado que los números válidos son aquellos que tienen casi 3 bits establecidos, encuéntrelos generando todas las secuencias de bits de 60 bits con menos o igual a 3 bits establecidos. Esto se puede hacer fijando, i th , j th y k th bits para todos los i, j, k de (0, 60). Una vez que todos los números válidos se generan en orden, aplique la búsqueda binaria para encontrar el recuento de los números que se encuentran dentro del rango dado.
A continuación se muestra la implementación del enfoque anterior.
C++
// CPP program to find the numbers
// having atmost 3 set bits within
// a given range
#include <bits/stdc++.h>
using namespace std;
#define LL long long int
// This function prints the required answer for each query
void answerQueries(LL Q, vector<pair<LL, LL> > query)
{
// Set of Numbers having at most 3 set bits
// arranged in non-descending order
set<LL> s;
// 0 set bits
s.insert(0);
// Iterate over all possible combinations of
// i, j and k for 60 bits
for (int i = 0; i <= 60; i++) {
for (int j = i; j <= 60; j++) {
for (int k = j; k <= 60; k++) {
// 1 set bit
if (j == i && i == k)
s.insert(1LL << i);
// 2 set bits
else if (j == k && i != j) {
LL x = (1LL << i) + (1LL << j);
s.insert(x);
}
else if (i == j && i != k) {
LL x = (1LL << i) + (1LL << k);
s.insert(x);
}
else if (i == k && i != j) {
LL x = (1LL << k) + (1LL << j);
s.insert(x);
}
// 3 set bits
else {
LL x = (1LL << i) + (1LL << j) + (1LL << k);
s.insert(x);
}
}
}
}
vector<LL> validNumbers;
for (auto val : s)
validNumbers.push_back(val);
// Answer Queries by applying binary search
for (int i = 0; i < Q; i++) {
LL L = query[i].first;
LL R = query[i].second;
// Swap both the numbers if L is greater than R
if (R < L)
swap(L, R);
if (L == 0)
cout << (upper_bound(validNumbers.begin(), validNumbers.end(),
R) - validNumbers.begin()) << endl;
else
cout << (upper_bound(validNumbers.begin(), validNumbers.end(),
R) - upper_bound(validNumbers.begin(), validNumbers.end(),
L - 1)) << endl;
}
}
// Driver Code
int main()
{
// Number of Queries
int Q = 2;
vector<pair<LL, LL> > query(Q);
query[0].first = 3;
query[0].second = 7;
query[1].first = 10;
query[1].second = 16;
answerQueries(Q, query);
return 0;
}
Java
// Java program to find the numbers
// having atmost 3 set bits within
// a given range
import java.util.*;
import java.io.*;
public class RangeQueries {
//Class to store the L and R range of a query
static class Query {
long L;
long R;
}
//It returns index of first element which is greater than searched value
//If searched element is bigger than any array element function
// returns first index after last element.
public static int upperBound(ArrayList<Long> validNumbers,
Long value)
{
int low = 0;
int high = validNumbers.size()-1;
while(low < high){
int mid = (low + high)/2;
if(value >= validNumbers.get(mid)){
low = mid+1;
} else {
high = mid;
}
}
return low;
}
public static void answerQueries(ArrayList<Query> queries){
// Set of Numbers having at most 3 set bits
// arranged in non-descending order
Set<Long> allNum = new HashSet<>();
//0 Set bits
allNum.add(0L);
//Iterate over all possible combinations of i, j, k for
// 60 bits. And add all the numbers with 0, 1 or 2 set bits into
// the set allNum.
for(int i=0; i<=60; i++){
for(int j=0; j<=60; j++){
for(int k=0; k<=60; k++){
//For one set bit, check if i, j, k are equal
//if yes, then set that bit and add it to the set
if(i==j && j==k){
allNum.add(1L << i);
}
//For two set bits, two of the three variable i,j,k
//will be equal and the third will not be. Set both
//the bits where two variables are equal and the bit
//which is not equal, and add it to the set
else if(i==j && j != k){
long toAdd = (1L << i) + (1L << k);
allNum.add(toAdd);
}
else if(i==k && k != j){
long toAdd = (1L << i) + (1L << j);
allNum.add(toAdd);
}
else if(j==k && k != i){
long toAdd = (1L << j) + (1L << i);
allNum.add(toAdd);
}
//Setting all the 3 bits
else {
long toAdd = (1L << i) + (1L << j) + (1L << k);
allNum.add(toAdd);
}
}
}
}
//Adding all the numbers to an array list so that it can be sorted
ArrayList<Long> validNumbers = new ArrayList<>();
for(Long num: allNum){
validNumbers.add(num);
}
Collections.sort(validNumbers);
//Answer queries by applying binary search
for(int i=0; i<queries.size(); i++){
long L = queries.get(i).L;
long R = queries.get(i).R;
//Swap L and R if R is smaller than L
if(R < L){
long temp = L;
L = R;
R = temp;
}
if(L == 0){
int indxOfLastNum = upperBound(validNumbers, R);
System.out.println(indxOfLastNum+1);
}
else {
int indxOfFirstNum = upperBound(validNumbers, L);
int indxOfLastNum = upperBound(validNumbers, R);
System.out.println((indxOfLastNum - indxOfFirstNum +1));
}
}
}
public static void main(String[] args){
int Q = 2;
ArrayList<Query> queries = new ArrayList<>();
Query q1 = new Query();
q1.L = 3;
q1.R = 7;
Query q2 = new Query();
q2.L = 10;
q2.R = 16;
queries.add(q1);
queries.add(q2);
answerQueries(queries);
}
}
Python3
#Python3 program to find the numbers # having atmost 3 set bits within # a given range import bisect # This function prints the required answer for each query def answerQueries(Q, query): # Set of Numbers having at most 3 set bits # arranged in non-descending order s = set() # 0 set bits s.add(0) # Iterate over all possible combinations of # i, j and k for 60 bits for i in range(61): for j in range(i, 61): for k in range(j, 61): # 1 set bit if (j == i and i == k): s.add(1 << i) # 2 set bits elif (j == k and i != j): x = (1 << i) + (1 << j) s.add(x) elif (i == j and i != k): x = (1 << i) + (1 << k) s.add(x) elif (i == k and i != j): x = (1 << k) + (1 << j) s.add(x) # 3 set bits else: x = (1 << i) + (1 << j) + (1 << k) s.add(x); validNumbers = [] for val in sorted(s): validNumbers.append(val) # Answer Queries by applying binary search for i in range(Q): L = query[i][0] R = query[i][1] # Swap both the numbers if L is greater than R if (R < L): L, R = R, L if (L == 0): print(bisect.bisect_right(validNumbers, R)) else: print(bisect.bisect_right(validNumbers, R) - bisect.bisect_right(validNumbers, L - 1)) # Driver Code #Number of Queries Q = 2 query = [[3, 7], [10, 16]] answerQueries(Q, query) #This code is contributed by phasing17
C#
// C# program to find the numbers
// having atmost 3 set bits within
// a given range
using System;
using System.Collections.Generic;
// Class to store the L and R range of a query
public class Query {
public long L;
public long R;
}
public class RangeQueries {
// It returns index of first element which is greater
// than searched value If searched element is bigger
// than any array element function returns first index
// after last element.
public static int upperBound(List<long> validNumbers,
long value)
{
int low = 0;
int high = validNumbers.Count - 1;
while (low < high) {
int mid = (low + high) / 2;
if (value >= validNumbers[mid]) {
low = mid + 1;
}
else {
high = mid;
}
}
return low;
}
public static void answerQueries(List<Query> queries)
{
// Set of Numbers having at most 3 set bits
// arranged in non-descending order
HashSet<long> allNum = new HashSet<long>();
// 0 Set bits
allNum.Add(0L);
// Iterate over all possible combinations of i, j, k
// for
// 60 bits. And add all the numbers with 0, 1 or 2
// set bits into the set allNum.
for (int i = 0; i <= 60; i++) {
for (int j = 0; j <= 60; j++) {
for (int k = 0; k <= 60; k++) {
// For one set bit, check if i, j, k are
// equal if yes, then set that bit and
// add it to the set
if (i == j && j == k) {
allNum.Add(1L << i);
}
// For two set bits, two of the three
// variable i,j,k will be equal and the
// third will not be. Set both the bits
// where two variables are equal and the
// bit which is not equal, and add it to
// the set
else if (i == j && j != k) {
long toAdd = (1L << i) + (1L << k);
allNum.Add(toAdd);
}
else if (i == k && k != j) {
long toAdd = (1L << i) + (1L << j);
allNum.Add(toAdd);
}
else if (j == k && k != i) {
long toAdd = (1L << j) + (1L << i);
allNum.Add(toAdd);
}
// Setting all the 3 bits
else {
long toAdd = (1L << i) + (1L << j)
+ (1L << k);
allNum.Add(toAdd);
}
}
}
}
// Adding all the numbers to an array list so that
// it can be sorted
List<long> validNumbers = new List<long>();
foreach(long num in allNum)
{
validNumbers.Add(num);
}
validNumbers.Sort();
// Answer queries by applying binary search
for (int i = 0; i < queries.Count; i++) {
long L = queries[i].L;
long R = queries[i].R;
// Swap L and R if R is smaller than L
if (R < L) {
long temp = L;
L = R;
R = temp;
}
if (L == 0) {
int indxOfLastNum
= upperBound(validNumbers, R);
Console.WriteLine(indxOfLastNum + 1);
}
else {
int indxOfFirstNum
= upperBound(validNumbers, L);
int indxOfLastNum
= upperBound(validNumbers, R);
Console.WriteLine(
(indxOfLastNum - indxOfFirstNum + 1));
}
}
}
// Driver code
public static void Main(string[] args)
{
List<Query> queries = new List<Query>();
Query q1 = new Query();
q1.L = 3;
q1.R = 7;
Query q2 = new Query();
q2.L = 10;
q2.R = 16;
queries.Add(q1);
queries.Add(q2);
// Function call
answerQueries(queries);
}
}
// This code is contributed by phasing.
Producción
5 6
Complejidad de tiempo : O ((Número máximo de bits) 3 + Q * logN), donde Q es el número de consultas y N es el tamaño del conjunto que contiene todos los números válidos. l números válidos.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA