Count numbers in range [L, R] having K consecutive set bits
Given three positive integers L, R, and K, the task is to find the count of numbers in the range [L, R] having K consecutive set bits in their binary representation.
Examples:
Input: L = 4, R = 15, K = 3
Output: 3
Explanation:
Numbers whose binary representation contains K(=3) consecutive set bits are:
(7)10 = (111)2
(14)10 = (1110)2
(15)10 = (1111)2
Therefore, the required output is 3.Input: L = 8, R = 100, K = 3
Output: 27
Naive Approach: The simplest approach to solve this problem to traverse all possible integers in the range [L, R] and for each number, check if binary representation of the number contains K consecutive 1s or not. If found to be true then print the number.
Time Complexity: O((R – L + 1) * 32)
Auxiliary Space: O(1)
Efficient Approach: The problem can be solved using Digit DP. The idea is to count of numbers having K consecutive 1s in the range [1, R] and subtract the count of the numbers having K consecutive 1s in the range [1, L – 1]. Following are the recurrence relations:
[Tex]= \sum^{1}_{i=0} cntN1X(len + 1, cntOne + i, KOne | (cntOne == K)) [/Tex]
cntN1X(len, cntOne, KOne): Stores the count of numbers in the range [1, X] with the following constraints:
len = length of binary representation of X.
cntOne = Count of consecutive 1s till index len.
KOne = Boolean value to check if K consecutive 1s present in X or not.
Follow the steps below to solve the problem:
- Initialize a 4D array dp[len][cntOne][KOne][tight] to compute and store the values of all subproblems of the above recurrence relation.
- Finally, return the value of dp[len][cntOne][KOne][tight].
Below is the implementation of the above approach:
C++
// C++ program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to find the count of numbers in // range[1, X] having K consecutive set bits int cntN1X(string str, int len, int K, int cntOne, int dp[32][32][2][2], bool KOne, bool tight) { // If length of current number is // equal to length of string if (len == str.length()) { // If count of consecutive set bits // in the current string is >= K return (KOne == 1); } // If already computedx // equal occurred if (dp[len][cntOne][KOne][tight] != -1) { return dp[len][cntOne][KOne][tight]; } // If tight is 1, then element present // at current index is element present // in str at current index. Otherwise, 1. int end = tight ? (str[len] - '0' ): 1; // Stores count of numbers whose // len th bit is i. int res = 0; // Iterate over all possible // value present at current index. for ( int i = 0; i <= end; i++) { // Stores count of consecutive 1s int temp = (i==1) ? (cntOne + 1): 0; // Update res. res += cntN1X(str, len + 1, K, temp, dp, (KOne | (temp == K)), (tight & (i==end))); } return dp[len][cntOne][KOne][tight] = res; } // Function to find // binary representation of N string convertBinary( int N) { // Stores binary // representation of N. string res; // Traverse each bit of N. while (N) { // Append current bit // in res res.push_back(N % 2 + '0' ); // Update N. N /= 2; } // Append 0 in binary representation // Of N while (res.length() < 32) { res.push_back( '0' ); } // Reverse binary representation of N reverse(res.begin(), res.end()); return res; } // Function to count numbers in // range[L, R] having K consecutive 1s. int cntN1XL_R( int L, int R, int K) { // Stores binary representation // of (L - 1) string Ls = convertBinary(L - 1); // Stores binary representation // of R string Rs = convertBinary(R); // Stores values of overlapping // subproblems int dp[32][32][2][2]; // Initialize dp[][][][] array. memset (dp, -1, sizeof (dp)); // Stores count of numbers from // [1, L - 1] having K consecutive 1s int resL = cntN1X(Ls, 0, K, 0, dp, 0,1); // Initialize dp[][][][] array. memset (dp, -1, sizeof (dp)); // Stores count of numbers from // [1, R - 1] having K consecutive 1s int resR = cntN1X(Rs, 0, K, 0, dp, 0, 1); // Return total counts having K // consecutive 1s in range[L, R] return (resR - resL); } // Driver Code int main() { int L = 8; int R = 100; int K = 3; cout<<cntN1XL_R(L, R, K); } |
Java
// Java program to implement // the above approach import java.util.*; class GFG{ // Function to find the count of numbers in // range[1, X] having K consecutive set bits public static int cntN1X(String str, int len, int K, int cntOne, int dp[][][][], int KOne, int tight) { // If length of current number is // equal to length of string if (len == str.length()) { // If count of consecutive set bits // in the current string is >= K return (KOne == 1 ) ? 1 : 0 ; } // If already computedx // equal occurred if (dp[len][cntOne][KOne][tight] != - 1 ) { return dp[len][cntOne][KOne][tight]; } // If tight is 1, then element present // at current index is element present // in str at current index. Otherwise, 1. int end = (tight == 1 ) ? (str.charAt(len) - '0' ) : 1 ; // Stores count of numbers whose // len th bit is i. int res = 0 ; // Iterate over all possible // value present at current index. for ( int i = 0 ; i <= end; i++) { // Stores count of consecutive 1s int temp = (i == 1 ) ? (cntOne + 1 ) : 0 ; // Update res. res += cntN1X(str, len + 1 , K, temp, dp, ( int )(KOne | ((temp == K) ? 1 : 0 )), ( int )(tight & ((i == end) ? 1 : 0 ))); } return dp[len][cntOne][KOne][tight] = res; } // Function to count numbers in // range[L, R] having K consecutive 1s. public static int cntN1XL_R( int L, int R, int K) { // Stores binary representation // of (L - 1) String Ls = Integer.toBinaryString(L - 1 ); // Stores binary representation // of R String Rs = Integer.toBinaryString(R); // Stores values of overlapping // subproblems int dp[][][][] = new int [ 32 ][ 32 ][ 2 ][ 2 ]; // Initialize dp[][][][] array. for ( int i[][][] : dp) for ( int j[][] : i) for ( int k[] : j) Arrays.fill(k, - 1 ); // Stores count of numbers from // [1, L - 1] having K consecutive 1s int resL = cntN1X(Ls, 0 , K, 0 , dp, 0 , 1 ); // Initialize dp[][][][] array. for ( int i[][][] : dp) for ( int j[][] : i) for ( int k[] : j) Arrays.fill(k, - 1 ); // Stores count of numbers from // [1, R - 1] having K consecutive 1s int resR = cntN1X(Rs, 0 , K, 0 , dp, 0 , 1 ); // Return total counts having K // consecutive 1s in range[L, R] return (resR - resL); } // Driver Code public static void main(String args[]) { int L = 8 ; int R = 100 ; int K = 3 ; System.out.println(cntN1XL_R(L, R, K)); } } // This code is contributed by hemanth gadarla |
Python3
# Python3 program to implement # the above approach # Function to find the count of numbers in # range[1, X] having K consecutive set bits def cntN1X(stri, leng, K, cntOne, dp, KOne, tight): # If length of current number is # equal to length of string if (leng = = len (stri)): # If count of consecutive set bits # in the current string is >= K return 1 if (KOne = = 1 ) else 0 ; # If already computedx # equal occurred if (dp[leng][cntOne][KOne][tight] ! = - 1 ): return dp[leng][cntOne][KOne][tight]; # If tight is 1, then element present # at current index is element present # in stri at current index. Otherwise, 1. end = ( ord (stri[leng]) - ord ( '0' )) if tight = = 1 else 1 ; # Stores count of numbers whose # leng th bit is i. res = 0 ; # Iterate over all possible # value present at current index. for i in range (end + 1 ): # Stores count of consecutive 1s temp = (cntOne + 1 ) if (i = = 1 ) else 0 ; # Update res. res + = cntN1X(stri, leng + 1 , K, temp, dp, 1 if (KOne | (temp = = K)) else 0 , 1 if (tight & (i = = end)) else 0 ); dp[leng][cntOne][KOne][tight] = res return res # Function to find # binary representation of N def convertBinary(N): # Stores binary # representation of N. res = '' # Traverse each bit of N. while (N ! = 0 ): # Append current bit # in res res + = chr ((N % 2 ) + ord ( '0' )); # Update N. N / / = 2 ; # Append 0 in binary representation # Of N while ( len (res) < 32 ): res + = '0' ; # Reverse binary representation of N return res[:: - 1 ]; # Function to count numbers in # range[L, R] having K consecutive 1s. def cntN1XL_R(L, R, K): # Stores binary representation # of (L - 1) Ls = str (convertBinary(L - 1 )); # Stores binary representation # of R Rs = str (convertBinary(R)); # Stores values of overlapping # subproblems dp = [[[[ - 1 , - 1 ] for j in range ( 2 )] for k in range ( 32 )] for l in range ( 32 )] # Stores count of numbers from # [1, L - 1] having K consecutive 1s resL = cntN1X(Ls, 0 , K, 0 , dp, 0 , 1 ); # Initialize dp[][][][] array. dp = [[[[ - 1 , - 1 ] for j in range ( 2 )] for k in range ( 32 )] for l in range ( 32 )] # Stores count of numbers from # [1, R - 1] having K consecutive 1s resR = cntN1X(Rs, 0 , K, 0 , dp, 0 , 1 ); # Return total counts having K # consecutive 1s in range[L, R] return (resR - resL); # Driver Code if __name__ = = '__main__' : L = 8 ; R = 100 ; K = 3 ; print (cntN1XL_R(L, R, K)) # This code is contributed by rutvik_56 |
C#
// C# program to implement // the above approach using System; class GFG{ // Function to find the count of numbers in // range[1, X] having K consecutive set bits public static int cntN1X(String str, int len, int K, int cntOne, int [,,,]dp, int KOne, int tight) { // If length of current number is // equal to length of string if (len == str.Length) { // If count of consecutive set bits // in the current string is >= K return (KOne == 1) ? 1 : 0; } // If already computedx // equal occurred if (dp[len, cntOne, KOne, tight] != -1) { return dp[len, cntOne, KOne, tight]; } // If tight is 1, then element present // at current index is element present // in str at current index. Otherwise, 1. int end = (tight == 1) ? (str[len] - '0' ) : 1; // Stores count of numbers whose // len th bit is i. int res = 0; // Iterate over all possible // value present at current index. for ( int i = 0; i <= end; i++) { // Stores count of consecutive 1s int temp = (i == 1) ? (cntOne + 1) : 0; // Update res. res += cntN1X(str, len + 1, K, temp, dp, ( int )(KOne | ((temp == K) ? 1 : 0)), ( int )(tight & ((i == end) ? 1 : 0))); } return dp[len, cntOne, KOne, tight] = res; } // Function to count numbers in // range[L, R] having K consecutive 1s. public static int cntN1XL_R( int L, int R, int K) { // Stores binary representation // of (L - 1) String Ls = Convert.ToString(L - 1, 2); // Stores binary representation // of R String Rs = Convert.ToString(R, 2); // Stores values of overlapping // subproblems int [,,,]dp = new int [ 32, 32, 2, 2 ]; // Initialize [,]dp[,] array. for ( int i = 0; i < 32; i++) for ( int j = 0; j < 32; j++) for ( int k = 0; k < 2; k++) for ( int l = 0; l < 2; l++) dp[i, j, k, l] = -1; // Stores count of numbers from // [1, L - 1] having K consecutive 1s int resL = cntN1X(Ls, 0, K, 0, dp, 0, 1); // Initialize [,]dp[,] array. for ( int i = 0; i < 32; i++) for ( int j = 0; j < 32; j++) for ( int k = 0; k < 2; k++) for ( int l = 0; l < 2; l++) dp[i, j, k, l] = -1; // Stores count of numbers from // [1, R - 1] having K consecutive 1s int resR = cntN1X(Rs, 0, K, 0, dp, 0, 1); // Return total counts having K // consecutive 1s in range[L, R] return (resR - resL); } // Driver Code public static void Main(String []args) { int L = 8; int R = 100; int K = 3; Console.WriteLine(cntN1XL_R(L, R, K)); } } // This code is contributed by gauravrajput1 |
Javascript
<script> // JavaScript program to implement the above approach // Function to find the count of numbers in // range[1, X] having K consecutive set bits function cntN1X(str, len, K, cntOne, dp, KOne, tight) { // If length of current number is // equal to length of string if (len == str.length) { // If count of consecutive set bits // in the current string is >= K return (KOne == 1) ? 1 : 0; } // If already computedx // equal occurred if (dp[len][cntOne][KOne][tight] != -1) { return dp[len][cntOne][KOne][tight]; } // If tight is 1, then element present // at current index is element present // in str at current index. Otherwise, 1. let end = (tight == 1) ? (str[len].charCodeAt()- '0' .charCodeAt()) : 1; // Stores count of numbers whose // len th bit is i. let res = 0; // Iterate over all possible // value present at current index. for (let i = 0; i <= end; i++) { // Stores count of consecutive 1s let temp = (i == 1) ? (cntOne + 1) : 0; // Update res. res += cntN1X(str, len + 1, K, temp, dp, (KOne | ((temp == K) ? 1 : 0)), (tight & ((i == end) ? 1 : 0))); } dp[len][cntOne][KOne][tight] = res; return dp[len][cntOne][KOne][tight]; } // Function to count numbers in // range[L, R] having K consecutive 1s. function cntN1XL_R(L, R, K) { // Stores binary representation // of (L - 1) let Ls = (L - 1).toString(2); // Stores binary representation // of R let Rs = (R).toString(2); // Stores values of overlapping // subproblems let dp = new Array(32); // Initialize dp[][][][] array. for (let i = 0; i < 32; i++) { dp[i] = new Array(32); for (let j = 0; j < 32; j++) { dp[i][j] = new Array(2); for (let k = 0; k < 2; k++) { dp[i][j][k] = new Array(2); for (let l = 0; l < 2; l++) { dp[i][j][k][l] = -1; } } } } // Stores count of numbers from // [1, L - 1] having K consecutive 1s let resL = cntN1X(Ls, 0, K, 0, dp, 0, 1); // Initialize dp[][][][] array. for (let i = 0; i < 32; i++) { dp[i] = new Array(32); for (let j = 0; j < 32; j++) { dp[i][j] = new Array(2); for (let k = 0; k < 2; k++) { dp[i][j][k] = new Array(2); for (let l = 0; l < 2; l++) { dp[i][j][k][l] = -1; } } } } // Stores count of numbers from // [1, R - 1] having K consecutive 1s let resR = cntN1X(Rs, 0, K, 0, dp, 0, 1); // Return total counts having K // consecutive 1s in range[L, R] return (resR - resL); } let L = 8; let R = 100; let K = 3; document.write(cntN1XL_R(L, R, K)); </script> |
Output
27
Time complexity: O(32K(log(R) + log(L))), where K is the number of consecutive set bits and log(R) and log(L) represent the maximum number of bits in binary representation of R and L, respectively
Auxiliary Space: O(32K2*2)