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 precomputevoid 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 bitslong 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 Codeint 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 approachimport 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 approachimport bisect# Function to precomputedef 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 bitsdef 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 queriesdef 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 codearr = [(11, 19), (14, 19)]# Function callperform_query(arr)# This code is contributed by phasing17. |
C#
// C# code to implement the approachusing 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 precomputefunction 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 bitsfunction 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 queriesfunction 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 codelet arr = [ [11n, 19n], [14n, 19n]];// Function callperformQuery(arr);// This code is contributed by phasing17. |
Output
4 2
Time Complexity: O(N*log(633)+ 633)
Auxiliary Space: O(633)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
