# Count numbers in the range [L, R] having only three set bits

Given an array **arr[] **of **N** pairs, where each array element denotes a query of the form **{L, R}, ** the task is to find the count of numbers in the range** [L, R]**, having only 3-set bits for each query** {L, R}.**

**Examples:**

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

Input:arr[]={{11, 19}, {14, 19}}Output:4

2Explanation:

- Query(11, 19): Numbers in the range [11, 19] having three set bits are {11, 13, 14, 19}.
- Query(14, 19): Numbers in the range [14, 19] having three set bits are {14, 19}.

Input:arr[]={{1, 10}, {6, 12}}Output:1

2Explanation:

- Query(1, 10): Numbers in the range [1, 10] having three set bits are {7}.
- Query(6, 12): Numbers in the range [6, 12] having three set bits are {7, 12}.

**Approach: **The idea to solve this problem is to do a pre-computation and store all the numbers with only **3** bits set in the range **[1, 10 ^{18}]**, and then use binary search to find the position of lowerbound of

**L**and upperbound of

**R**and return the answer as there difference. Follow the steps below to solve the given problem:

- Initialize a vector, say
**V**, to store all the numbers in the range**[1, 10**with only three bits set.^{18}] - Iterate over every triplet formed of the relation
**[0, 63]×[0, 63]×[0, 63]**using variables**i, j**,**k**and perform the following steps:- If
**i, j**, and**k**are distinct, then compute the number with**i**and^{th}, j^{th},**k**bit set, and if the number is less than^{th}**10**^{18},^{ }push the number in the vector**V**.

- If
- Sort the vector V in ascending order.
- Traverse the array
**arr[],**using the variable**i,**and perform the following steps:- Store the boundaries of the query in the variables, say
**L**and**R**, respectively. - Find the position of the lowerbound of
**L**and upperbound of**R**in the vector**V**. - Print the difference between the positions of the upper bound of
**R**and the lower bound of**L**, as the result.

- Store the boundaries of the query in the variables, say

Below is the implementation of the above approach:

## 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; ` `}` |

**Output**

4 2

**Time Complexity:** *O(N*log(63*^{3}*)+ 63 ^{3})*

**Auxiliary Space:**O(63^{3})