|||| 5 6 7 8 9 Question 16 Range Queries 10 Given Q queries of type L R x, find the count of integers in range L to R (inclusive) which have their xth (from LSB side) bit ON. 11 Example 12 IfQ=2 13 14 15 • If L = 2, R = 10, x = 0. All odd numbers in range 2 to 10 have their Oth bit ON. Hence required answer is 4 Le 3, 5, 7, 9. Max score: 50.00 Function Description Complete the countInteger function provided in the editor. This function takes the following 3 parameters and returns the count of integers which satisfy condition mentioned in problem statement. 16 • If L = 20, R = 30, x=3. There are 7 numbers in range 20 to 30 which have their 3rd bit ON. The numbers are 24, 25, 26, 27, 28, 29 and 30. •L Represents the start of range • R Represents the end of range •x Represents the value of x Input 1. First line contain an integer Q denoting number of queries 2 Next Q lines contain three space separated integers LR x Constraints 1 write the program​

Answer:

• Create an array res[] where res[i] will store the count of valid integers from the range [0, i].
• Starting from 0, find the binary representation of all the integer and check whether the given pattern occurs in it.
• Update the res[] array based on the values found in the previous step.
• Now every query can be answered in O(1) as res[R] – res[L – 1].

Explanation:

#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