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:
Input: arr[] = {{11, 19}, {14, 19}}
Output: 4
2
Explanation:
- 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
2
Explanation:
- 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, 1018], and then use binary search to find the position of lowerbound of L and upperbound of R and return the answer as their difference. Follow the steps below to solve the given problem:
- Initialize a vector, say V, to store all the numbers in the range [1, 1018] with only three bits set.
- Iterate over every triplet formed of the relation [0, 63]×[0, 63]×[0, 63] using variables i, j, and k and perform the following steps:
- If i, j, and k are distinct, then compute the number with the ith, jth, and kth bit set, and if the number is less than 1018, push the number in the vector V.
- 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.
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; } |
Java
// Java code to implement the approach import java.util.ArrayList; import java.util.Collections; import java.util.List; class GFG { // Function to precompute static void precompute(List<Long> v) { // Iterate over the range [0, 64] for ( int i = 0 ; i < 64 ; i++) { // Iterate over the range [0, 64] for ( int j = i + 1 ; j < 64 ; j++) { // Iterate over the range [0, 64] for ( int k = j + 1 ; k < 64 ; k++) { // Store the number with i, j, k bits // set long x = ( long )(1L << i) | (1L << j) | (1L << k); // Check if the number is in valid range long limit = 1000000000000000000L; if (x <= limit && x > 0 ) { v.add(x); } } } } Collections.sort(v); } // Function to compute numbers in the range [l, r] // with three set bits static int query( long l, long r, List<Long> v) { // Finding lowerbound of l in v int x = Collections.binarySearch(v, l) - 1 ; // Finding upperbound of l in v int y = Collections.binarySearch(v, r); // Find difference between positions return y - x ; } // This function performs the queries static void perform_query(List< long []> arr) { // Stores the numbers List<Long> v = new ArrayList<>(); // Function call to perform the precomputation precompute(v); // Iterate over the query for ( long [] lr : arr) { // Print the answer System.out.println(query(lr[ 0 ], lr[ 1 ], v)); } } // Driver code public static void main(String[] args) { List< long []> arr = new ArrayList<>(); arr.add( new long [] { 11 , 19 }); arr.add( new long [] { 14 , 19 }); // Function call perform_query(arr); } } // This code is contributed by phasing17. |
Python3
# Python3 code to implement the approach import bisect # Function to precompute def precompute(v): # Iterate over the range [0, 64] for i in range ( 64 ): # Iterate over the range [0, 64] for j in range (i + 1 , 64 ): # Iterate over the range [0, 64] for k in range (j + 1 , 64 ): # Store the number with i, j, k bits set x = ( 1 << i) | ( 1 << j) | ( 1 << k) # Check if the number is in valid range if x < = 1e18 and x > 0 : v.append(x) v.sort() # Function to compute numbers in the range [l, r] # with three set bits def query(l, r, v): # Finding lowerbound of l in v x = bisect.bisect_left(v, l) # Finding upperbound of l in v y = bisect.bisect_right(v, r) # Find difference between positions return y - x # This function performs the queries def perform_query(arr): # Stores the numbers v = [] # Function call to perform the precomputation precompute(v) # Iterate over the query for l, r in arr: # Print the answer print (query(l, r, v)) # Driver code arr = [( 11 , 19 ), ( 14 , 19 )] # Function call perform_query(arr) # This code is contributed by phasing17. |
C#
// C# code to implement the approach using System; using System.Collections.Generic; class GFG { // Function to precompute static void precompute(List< long > v) { // Iterate over the range [0, 64] for ( int i = 0; i < 64; i++) { // Iterate over the range [0, 64] for ( int j = i + 1; j < 64; j++) { // Iterate over the range [0, 64] for ( int k = j + 1; k < 64; k++) { // Store the number with i, j, k bits set long x = ( long )(1L << i) | (1L << j) | (1L << k); // Check if the number is in valid range long limit = 1000000000000000000L; if (x <= limit && x > 0) { v.Add(x); } } } } v.Sort(); } // Function to compute numbers in the range [l, r] with three set bits static int query( long l, long r, List< long > v) { // Finding lowerbound of l in v int x = v.BinarySearch(l) - 1; // Finding upperbound of l in v int y = v.BinarySearch(r); // Find difference between positions return y - x; } // This function performs the queries static void perform_query(List< long []> arr) { // Stores the numbers List< long > v = new List< long >(); // Function call to perform the precomputation precompute(v); // Iterate over the query foreach ( long [] lr in arr) { // Print the answer Console.WriteLine(query(lr[0], lr[1], v)); } } // Driver code static void Main( string [] args) { List< long []> arr = new List< long []>(); arr.Add( new long [] { 11, 19 }); arr.Add( new long [] { 14, 19 }); // Function call perform_query(arr); } } // This code is contributed by phasing17. |
Javascript
// Javascript code to implement the approach // Function to precompute function precompute(v) { // Iterate over the range [0, 64] for (let i = 0; i < 64; i++) { // Iterate over the range [0, 64] for (let j = i + 1; j < 64; j++) { // Iterate over the range [0, 64] for (let k = j + 1; k < 64; k++) { // Store the number with i, j, k bits set let x = BigInt(2n ** BigInt(i)) | BigInt(2n ** BigInt(j)) | BigInt(2n ** BigInt(k)); // Check if the number is in valid range if (x <= BigInt(1e18) && x > 0n) { v.push(x); } } } } v.sort((a, b) => { if (a > b) { return 1; } else if (a < b) { return -1; } else { return 0; } }); } // Function to compute numbers in the range [l, r] // with three set bits function query(l, r, v) { // Finding lowerbound of l in v let x = v.findIndex(n => n >= l); // Finding upperbound of l in v let y = v.findIndex(n => n > r); // Find difference between positions return y - x; } // This function performs the queries function performQuery(arr) { // Stores the numbers let v = []; // Function call to perform the precomputation precompute(v); // Iterate over the query for (const [l, r] of arr) { // Print the answer console.log(query(l, r, v)); } } // Driver code let arr = [ [11n, 19n], [14n, 19n] ]; // Function call performQuery(arr); // This code is contributed by phasing17. |
4 2
Time Complexity: O(N*log(633)+ 633)
Auxiliary Space: O(633)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!