Given integers L and R, the task is to find the number of integers in the range L to R whose bitwise OR of digits is exactly K. Print the answer.
Examples:
Input: L = 1, R = 15, K =5
Output: 3
Explanation:
- For number 5 its bitwise OR of digits will be 5
- For number 14 its bitwise OR of digits will be 5
- for number 15 its bitwise OR of digits will be 5
Total three numbers 5, 14 and 15 are there whose bitwise OR of digits is exactly K = 5
Input: L = 1, R = 100, K = 5
Output: 9
Naive approach: The basic way to solve the problem is as follows:
The basic way to solve this problem is to generate all possible combinations by using a recursive approach.
Time Complexity: O(N10)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized based on the following idea:
Dynamic programming can be used to solve this problem:
- dp[i][j][k] represents numbers in the range with i digits, j represents the tight condition and k represents the current bitwise OR sum.
- It can be observed that the recursive function is called exponential times.
- That means that some states are called repeatedly. So the idea is to store the value of each state. This can be done using by the store the value of a state and whenever the function is called, returning the stored value without computing again.
- The first answer will be calculated for 0 to L – 1 and then calculated for 0 to R then the latter one is subtracted from the prior one to get an answer for range [L, R]
Follow the steps below to solve the problem:
- Create a recursive function that takes three parameters i representing position to be filled, j representing tight condition, and k representing bitwise OR sum of digits.
- Call the recursive function for choosing all digits from 0 to 9.
- In the base case, if the size of the digit is N and bitwise OR sum is K return 1 otherwise return 0.
- Create a 3d array dp[100001][2][16] initially filled with -1.
- If the answer for a particular state is computed then save it in dp[i][j][k].
- if the answer for a particular state is already computed then just return dp[i][j][k].
Below is the implementation of the above approach:
C++14
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// DP table initialized with -1int dp[100001][2][16];// Recursive Function to find numbers// in the range L to R such that its// bitwise OR is K.int recur(int i, int j, int k, int T, string& a){ // Base case if (i == a.size()) { // If bitwise OR is K if (k == T) return 1; // Otherwise return 0 else return 0; } // If answer for current state is // already calculated then just // return dp[i][j][k] if (dp[i][j][k] != -1) return dp[i][j][k]; // Answer initialized with zero int ans = 0; // Tight condition true if (j == 1) { // Iterating from 0 to max value // of tight condition for (int digit = 0; digit <= ((int)a[i] - 48); digit++) { // When digit is at max tight // condition remains even // in next state if (digit == ((int)a[i] - 48)) // Calling recursive function // for tight digit ans += recur(i + 1, 1, k | digit, T, a); // Tight condition drops else if (digit != 0) // Calling recursive function // for digits less than tight // condition digit ans += recur(i + 1, 0, k | digit, T, a); else // Calling recursive // function for 0 ans += recur(i + 1, 0, k | digit, T, a); } } // Tight condition false else { // Iterating for all digits for (int digit = 0; digit <= 9; digit++) { // Calling recursive function // for all digits from 0 to 9 ans += recur(i + 1, 0, k | digit, T, a); } } // Save and return dp value return dp[i][j][k] = ans;}// Function to find numbers// in the range L to R such that its// bitwise OR is K.int countInRange(int K, int A, int B){ // Initializing dp array with - 1 memset(dp, -1, sizeof(dp)); A--; string L = to_string(A), R = to_string(B); // Numbers with bitwise OR sum of // digits K in the range 0 to L int ans1 = recur(0, 1, 0, K, L); // Initializing dp array with - 1 memset(dp, -1, sizeof(dp)); // Numbers with bitwise OR sum of // digits K in the range 0 to R int ans2 = recur(0, 1, 0, K, R); // Difference of ans2 and ans1 // will generate answer for // required range return ans2 - ans1;}// Driver Codeint main(){ // Input 1 int L = 1, R = 20, K = 5; // Function Call cout << countInRange(K, L, R) << endl; // Input 2 int L1 = 1, R1 = 100, K1 = 5; // Function Call cout << countInRange(K1, L1, R1) << endl; return 0;} |
Java
// Java code to implement the approachimport java.io.*;import java.util.*;class GFG { // DP table initialized with -1 static int[][][] dp = new int[100001][2][16]; // Recursive Function to find numbers // in the range L to R such that its // bitwise OR is K. static int recur(int i, int j, int k, int T, String a) { // Base case if (i == a.length()) { // If bitwise OR is K if (k == T) { return 1; } // Otherwise return 0 else { return 0; } } // If answer for current state is // already calculated then just // return dp[i][j][k] if (dp[i][j][k] != -1) { return dp[i][j][k]; } // Answer initialized with zero int ans = 0; // Tight condition true if (j == 1) { // Iterating from 0 to max value // of tight condition for (int digit = 0; digit <= (a.charAt(i) - '0'); digit++) { // When digit is at max tight // condition remains even // in next state if (digit == (a.charAt(i) - '0')) { // Calling recursive function // for tight digit ans += recur(i + 1, 1, k | digit, T, a); } // Tight condition drops else if (digit != 0) { // Calling recursive function // for digits less than tight // condition digit ans += recur(i + 1, 0, k | digit, T, a); } else { // Calling recursive // function for 0 ans += recur(i + 1, 0, k | digit, T, a); } } } // Tight condition false else { // Iterating for all digits for (int digit = 0; digit <= 9; digit++) { // Calling recursive function // for all digits from 0 to 9 ans += recur(i + 1, 0, k | digit, T, a); } } // Save and return dp value return dp[i][j][k] = ans; } // Function to find numbers // in the range L to R such that its // bitwise OR is K. static int countInRange(int K, int A, int B) { // Initializing dp array with - 1 for (int[][] dp1 : dp) { for (int[] dp11 : dp1) { Arrays.fill(dp11, -1); } } A--; String L = Integer.toString(A), R = Integer.toString(B); // Numbers with bitwise OR sum of // digits K in the range 0 to L int ans1 = recur(0, 1, 0, K, L); // Initializing dp array with - 1 for (int[][] dp1 : dp) { for (int[] dp11 : dp1) { Arrays.fill(dp11, -1); } } // Numbers with bitwise OR sum of // digits K in the range 0 to R int ans2 = recur(0, 1, 0, K, R); // Difference of ans2 and ans1 // will generate answer for // required range return ans2 - ans1; } public static void main(String[] args) { // Input 1 int L = 1, R = 20, K = 5; // Function Call System.out.println(countInRange(K, L, R)); // Input 2 int L1 = 1, R1 = 100, K1 = 5; // Function Call System.out.println(countInRange(K1, L1, R1)); }}// This code is contributed by lokesh. |
Python3
# Python3 code to implement the approach# DP table initialized with -1dp = [[[-1 for _ in range(16)] for _ in range(2)] for _ in range(100001)]# Recursive Function to find numbers# in the range L to R such that its# bitwise OR is K.def recur(i, j, k, T, a): # Base case if i == len(a): # If bitwise OR is K if k == T: return 1 # Otherwise return 0 else: return 0 # If answer for current state is # already calculated then just # return dp[i][j][k] if dp[i][j][k] != -1: return dp[i][j][k] # Answer initialized with zero ans = 0 # Tight condition true if j == 1: # Iterating from 0 to max value # of tight condition for digit in range(int(a[i])+1 if int(a[i]) < 9 else 10): # When digit is at max tight # condition remains even # in next state if digit == int(a[i]): # Calling recursive function # for tight digit ans += recur(i + 1, 1, k | digit, T, a) # Tight condition drops elif digit != 0: # Calling recursive function # for digits less than tight # condition digit ans += recur(i + 1, 0, k | digit, T, a) else: # Calling recursive # function for 0 ans += recur(i + 1, 0, k | digit, T, a) # Tight condition false else: # Iterating for all digits for digit in range(10): # Calling recursive function # for all digits from 0 to 9 ans += recur(i + 1, 0, k | digit, T, a) # Save and return dp value dp[i][j][k] = ans return ans# Function to find numbers# in the range L to R such that its# bitwise OR is K.def countInRange(K, A, B): # Initializing dp array with - 1 global dp dp = [[[-1 for _ in range(16)] for _ in range(2)] for _ in range(100001)] A -= 1 L = str(A) R = str(B) # Numbers with bitwise OR sum of # digits K in the range 0 to L ans1 = recur(0, 1, 0, K, L) # Initializing dp array with - 1 dp = [[[-1 for _ in range(16)] for _ in range(2)] for _ in range(100001)] # Numbers with bitwise OR sum of # digits K in the range 0 to R ans2 = recur(0, 1, 0, K, R) # Difference of ans2 and ans1 # will generate answer for # required range return ans2-ans1# Driver codedef main(): L = 1 R = 20 K = 5 print(countInRange(K, L, R)) L1 = 1 R1 = 100 K1 = 5 print(countInRange(K1, L1, R1))if __name__ == "__main__": main() # This code is contributed by unstoppablepandu. |
C#
// C# code to implement the approachusing System;public class GFG { // DP table initialized with -1 static int[, , ] dp = new int[100001, 2, 16]; // Recursive Function to find numbers // in the range L to R such that its // bitwise OR is K. static int recur(int i, int j, int k, int T, string a) { // Base case if (i == a.Length) { // If bitwise OR is K if (k == T) { return 1; } // Otherwise return 0 else { return 0; } } // If answer for current state is // already calculated then just // return dp[i][j][k] if (dp[i, j, k] != -1) { return dp[i, j, k]; } // Answer initialized with zero int ans = 0; // Tight condition true if (j == 1) { // Iterating from 0 to max value // of tight condition for (int digit = 0; digit <= (a[i] - '0'); digit++) { // When digit is at max tight // condition remains even // in next state if (digit == (a[i] - '0')) { // Calling recursive function // for tight digit ans += recur(i + 1, 1, k | digit, T, a); } // Tight condition drops else if (digit != 0) { // Calling recursive function // for digits less than tight // condition digit ans += recur(i + 1, 0, k | digit, T, a); } else { // Calling recursive // function for 0 ans += recur(i + 1, 0, k | digit, T, a); } } } // Tight condition false else { // Iterating for all digits for (int digit = 0; digit <= 9; digit++) { // Calling recursive function // for all digits from 0 to 9 ans += recur(i + 1, 0, k | digit, T, a); } } // Save and return dp value return dp[i, j, k] = ans; } // Function to find numbers // in the range L to R such that its // bitwise OR is K. static int countInRange(int K, int A, int B) { // Initializing dp array with - 1 for (int i = 0; i < dp.GetLength(0); i++) { for (int j = 0; j < dp.GetLength(1); j++) { for (int k = 0; k < dp.GetLength(2); k++) { dp[i, j, k] = -1; } } } A--; string L = A.ToString(); string R = B.ToString(); // Numbers with bitwise OR sum of // digits K in the range 0 to L int ans1 = recur(0, 1, 0, K, L); // Initializing dp array with - 1 for (int i = 0; i < dp.GetLength(0); i++) { for (int j = 0; j < dp.GetLength(1); j++) { for (int k = 0; k < dp.GetLength(2); k++) { dp[i, j, k] = -1; } } } // Numbers with bitwise OR sum of // digits K in the range 0 to R int ans2 = recur(0, 1, 0, K, R); // Difference of ans2 and ans1 // will generate answer for // required range return ans2 - ans1; } static public void Main() { // Code // Input 1 int L = 1, R = 20, K = 5; // Function Call Console.WriteLine(countInRange(K, L, R)); // Input 2 int L1 = 1, R1 = 100, K1 = 5; // Function Call Console.WriteLine(countInRange(K1, L1, R1)); }}// This code is contributed by lokeshmvs21. |
Javascript
let dp = Array.from({ length: 100001 }, () => Array.from({ length: 2 }, () => Array.from({ length: 16 }, () => -1)));function recur(i, j, k, T, a) { // Base case if (i == a.length) { // If bitwise OR is K if (k == T) { return 1; } // Otherwise return 0 else { return 0; } } // If answer for current state is already // calculated then just return dp[i][j][k] if (dp[i][j][k] != -1) { return dp[i][j][k]; } // Answer initialized with zero let ans = 0; // Tight condition true if (j == 1) { // Iterating from 0 to max value of tight condition for (let digit = 0; digit <= (parseInt(a[i]) < 9 ? parseInt(a[i]) : 9); digit++) { // When digit is at max tight condition remains even in next state if (digit == parseInt(a[i])) { // Calling recursive function for tight digit ans += recur(i + 1, 1, k | digit, T, a); } // Tight condition drops for digits less than tight condition digit else if (digit != 0) { // Calling recursive function for digits less than tight condition digit ans += recur(i + 1, 0, k | digit, T, a); } else { // Calling recursive function for 0 ans += recur(i + 1, 0, k | digit, T, a); } } } // Tight condition false else { // Iterating for all digits for (let digit = 0; digit <= 9; digit++) { // Calling recursive function for all digits from 0 to 9 ans += recur(i + 1, 0, k | digit, T, a); } } // Save and return dp value dp[i][j][k] = ans; return ans;}function countInRange(K, A, B) { // Initializing dp array with -1 dp = Array.from({ length: 100001 }, () => Array.from({ length: 2 }, () => Array.from({ length: 16 }, () => -1))); A -= 1; let L = A.toString(); let R = B.toString(); // Numbers with bitwise OR sum of digits K in the range 0 to L let ans1 = recur(0, 1, 0, K, L); // Initializing dp array with -1 dp = Array.from({ length: 100001 }, () => Array.from({ length: 2 }, () => Array.from({ length: 16 }, () => -1))); // Numbers with bitwise OR sum of digits K in the range 0 to R let ans2 = recur(0, 1, 0, K, R); // Difference of ans2 and ans1 will generate answer for required range return ans2 - ans1;}// Driver code let L = 1; let R = 20; let K = 5; console.log(countInRange(K, L, R)); let L1 = 1; let R1 = 100; let K1 = 5; console.log(countInRange(K1, L1, R1)); |
Output
3 9
Time Complexity: O(log(R – L))
Auxiliary Space: O(log(R – L))
Related Articles:
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!
Share your thoughts in the comments
