Given a binary pattern patt and Q queries where each query consists of a range [L, R], for every query the task is to find the count of integers from the given range such that they contain the given pattern in their binary representation.
Examples:
Input: q[][] = {{2, 10}}, patt = “101”
Output:
2
5(101) and 10(1010) are the only valid integers.
Input: q[][] = {{122, 150}, {18, 1000}}, patt = “1111”
Output:
7
227
Approach:
- 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].
Below is the implementation of the above approach:
C++
#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 queriesvoid 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 codeint 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
// Java implementation of the approachimport 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
# 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#
// C# implementation of the approachusing 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 |
Javascript
<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 queriesfunction 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 codelet queries=[[ 2, 10 ], [ 8, 120 ]];let q = queries.length;let pattern = "101";performQueries(queries, q, pattern);// This code is contributed by avanitrachhadiya2155</script> |
Output:
2 59
Time Complexity: O(q+max*log(max))
Auxiliary Space: O(max)
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!
