Consultas para encontrar el recuento de enteros en un rango que contiene el patrón dado

Dado un patrón binario patt y Q consultas donde cada consulta consta de un rango [L, R] , para cada consulta la tarea es encontrar el recuento de enteros del rango dado de modo que contengan el patrón dado en su representación binaria.
Ejemplos: 

Entrada: q[][] = {{2, 10}}, patt = “101” 
Salida: 
2 
5(101) y 10(1010) son los únicos números enteros válidos.
Entrada: q[][] = {{122, 150}, {18, 1000}}, patt = “1111” 
Salida: 
7 
227 

Acercarse: 

• Cree una array res[] donde res[i] almacenará el recuento de enteros válidos del rango [0, i] .
• A partir de 0 , encuentre la representación binaria de todos los enteros y verifique si el patrón dado ocurre en él.
• Actualice la array res[] según los valores encontrados en el paso anterior.
• Ahora cada consulta se puede responder en O(1) como res[R] – res[L – 1] .

A continuación se muestra la implementación del enfoque anterior: 
 

#include<bits/stdc++.h>
using namespace std;
 
// Function to return the
// pre-calculate array such
// that arr[i] stores the count of
// valid numbers in the range [0, i]
string DecimalToBinaryString(int a)
{
  string binary = "";
  int mask = 1;
  for (int i = 0; i < 31; i++)
  {
    if(mask&a)
      binary = "1" + binary;
    else
      binary = "0" + binary;
    mask <<= 1;
  }
 
  return binary;
}
 
vector<int> preCalculate(int max,
                         string pattern)
{
  vector<int> arr(max + 1, 0);
 
  // If 0 is a valid number
  if (pattern == "0")
    arr[0] = 1;
  else
    arr[0] = 0;
 
  // For every element i
  for (int i = 1; i <= max; i++)
  {
    // If i is avalid number
    if (DecimalToBinaryString(i).find(pattern) !=
        std::string :: npos)
    {
      arr[i] = 1 + arr[i - 1];
    }
    else
    {
      arr[i] = arr[i - 1];
    }
  }
  return arr;
}
 
// Function to perform the queries
void performQueries(vector<vector<int> > queries,
                    int q, string pattern)
{
  // Maximum value for the
  // end of any range
  int ma = INT_MIN;
   
  for (int i = 0; i < q; i++)
    ma = max(ma, queries[i][1]);
 
  // res[i] stores the count of valid
  // integers from the range [0, i]
  vector<int> res = preCalculate(ma,
                                 pattern);
 
  for (int i = 0; i < q; i++)
  {
    int l = queries[i][0];
    int r = queries[i][1];
 
    if (l == 0)
      cout << (res[r]) << endl;
    else
      cout << (res[r] -
               res[l - 1]) << endl;
  }
}
 
// Driver code
int main()
{
  vector<vector<int>> queries = {{2, 10},
                                 {8, 120}};
  int q = queries.size();
  string pattern = "101";
  performQueries(queries, q, pattern);
}
 
// This code is contributed by grand_master

// Java implementation of the approach
import java.util.*;
class GFG {
 
    // Function to return the pre-calculate array
    // such that arr[i] stores the count of
    // valid numbers in the range [0, i]
    static int[] preCalculate(int max, String pattern)
    {
        int arr[] = new int[max + 1];
 
        // If 0 is a valid number
        if (pattern == "0")
            arr[0] = 1;
        else
            arr[0] = 0;
 
        // For every element i
        for (int i = 1; i <= max; i++) {
 
            // If i is avalid number
            if (Integer.toBinaryString(i).contains(pattern)) {
                arr[i] = 1 + arr[i - 1];
            }
            else {
                arr[i] = arr[i - 1];
            }
        }
        return arr;
    }
 
    // Function to perform the queries
    static void performQueries(int queries[][],
                               int q, String pattern)
    {
 
        // Maximum value for the end of any range
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < q; i++)
            max = Math.max(max, queries[i][1]);
 
        // res[i] stores the count of valid
        // integers from the range [0, i]
        int res[] = preCalculate(max, pattern);
 
        for (int i = 0; i < q; i++) {
            int l = queries[i][0];
            int r = queries[i][1];
 
            if (l == 0)
                System.out.println(res[r]);
            else
                System.out.println(res[r] - res[l - 1]);
        }
    }
 
    // Driver code
    public static void main(String args[])
    {
        int queries[][] = { { 2, 10 }, { 8, 120 } };
        int q = queries.length;
        String pattern = "101";
 
        performQueries(queries, q, pattern);
    }
}

# Python3 implementation of the approach
import sys
 
# Function to return the pre-calculate array
# such that arr[i] stores the count of
# valid numbers in the range [0, i]
def preCalculate(maX, pattern) :
    arr = [0] * (maX + 1);
     
    # If 0 is a valid number
    if (pattern == "0") :
        arr[0] = 1;
         
    else :
        arr[0] = 0;
         
    # For every element i
    for i in range(1, maX + 1) :
         
        # If i is avalid number
        if (pattern in bin(i)) :
            arr[i] = 1 + arr[i - 1];
             
        else :
            arr[i] = arr[i - 1];
             
    return arr;
 
# Function to perform the queries
def performQueries(queries,q, pattern) :
     
    # Maximum value for the end of any range
    maX = -(sys.maxsize + 1);
     
    for i in range(q) :
         
        maX = max(maX, queries[i][1]);
         
    # res[i] stores the count of valid
    # integers from the range [0, i]
    res = preCalculate(maX, pattern);
 
    for i in range(q) :
        l = queries[i][0];
        r = queries[i][1];
         
        if (l == 0) :
            print(res[r]);
        else :
            print(res[r] - res[l - 1]);
 
# Driver code
if __name__ == "__main__" :
     
    queries = [ [ 2, 10 ], [ 8, 120 ] ];
    q = len(queries);
    pattern = "101";
    performQueries(queries, q, pattern);
 
# This code is contributed by kanugargng

// C# implementation of the approach
using System;
using System.Numerics;
 
class GFG
{
 
    //integer to binary string
    public static string toBinaryString(int x)
    {
        char[] bits = new char[32];
        int i = 0;
     
        while (x != 0)
        {
            bits[i++] = (x & 1) == 1 ? '1' : '0';
            x >>= 1;
        }
     
        Array.Reverse(bits, 0, i);
        return new string(bits);
    }
     
    // Function to return the pre-calculate array
    // such that arr[i] stores the count of
    // valid numbers in the range [0, i]
    static int[] preCalculate(int max, string pattern)
    {
        int []arr = new int[max + 1];
 
        // If 0 is a valid number
        if (pattern == "0")
            arr[0] = 1;
        else
            arr[0] = 0;
 
        // For every element i
        for (int i = 1; i <= max; i++)
        {
            // If i is avalid number
            if (toBinaryString(i).Contains(pattern))
            {
                arr[i] = 1 + arr[i - 1];
            }
            else
            {
                arr[i] = arr[i - 1];
            }
        }
        return arr;
    }
 
    // Function to perform the queries
    static void performQueries(int [,]queries,
                               int q, string pattern)
    {
 
        // Maximum value for the end of any range
        int max = int.MinValue;
        for (int i = 0; i < q; i++)
            max = Math.Max(max, queries[i, 1]);
 
        // res[i] stores the count of valid
        // integers from the range [0, i]
        int []res = preCalculate(max, pattern);
 
        for (int i = 0; i < q; i++)
        {
            int l = queries[i, 0];
            int r = queries[i, 1];
 
            if (l == 0)
                Console.WriteLine(res[r]);
            else
                Console.WriteLine(res[r] - res[l - 1]);
        }
    }
 
    // Driver code
    public static void Main(string []args)
    {
        int [,]queries = { { 2, 10 }, { 8, 120 } };
        int q = queries.GetLength(0) ;
        string pattern = "101";
 
        performQueries(queries, q, pattern);
    }
}
 
// This code is contributed by Arnab Kundu

<script>
 
// JavaScript implementation of the approach
 
// Function to return the pre-calculate array
    // such that arr[i] stores the count of
    // valid numbers in the range [0, i]
function preCalculate(max,pattern)
{
    let arr = new Array(max + 1);
  
        // If 0 is a valid number
        if (pattern == "0")
            arr[0] = 1;
        else
            arr[0] = 0;
  
        // For every element i
        for (let i = 1; i <= max; i++) {
  
            // If i is avalid number
            if ((i >>> 0).toString(2).includes(pattern)) {
                arr[i] = 1 + arr[i - 1];
            }
            else {
                arr[i] = arr[i - 1];
            }
        }
        return arr;
}
 
 // Function to perform the queries
function performQueries(queries,q,pattern)
{
    // Maximum value for the end of any range
        let max = Number.MIN_VALUE;
        for (let i = 0; i < q; i++)
            max = Math.max(max, queries[i][1]);
  
        // res[i] stores the count of valid
        // integers from the range [0, i]
        let res = preCalculate(max, pattern);
  
        for (let i = 0; i < q; i++) {
            let l = queries[i][0];
            let r = queries[i][1];
  
            if (l == 0)
                document.write(res[r]+"<br>");
            else
                document.write(res[r] - res[l - 1]+"<br>");
        }
}
 
// Driver code
let queries=[[ 2, 10 ], [ 8, 120 ]];
let q = queries.length;
let pattern = "101";
 
performQueries(queries, q, pattern);
 
 
// This code is contributed by avanitrachhadiya2155
 
</script>

2
59