Given two positive integers ‘L’ and ‘R‘, the task is to return the number of the integers in the range [L, R] inclusive, whose binary representations do not contain consecutive ones where 0 ≤ l ≤ r ≤ 10^9
Examples:
Input: L = 0, R = 3
Output: 3
Explanation: The 3 numbers are 0(00), 1(01), 2(10) 3(11) is not included as its binary representation contains consecutive onesInput: L = 5, R = 10
Output: 4
Explanation: The 4 numbers are 5(101), 8(1000), 9(1001), 10(1010)
Solving problem using Digit Dynamic Programming:
If we say G(x) tells the number of such integers between 0 to x (inclusively) without consecutive 1’s in their binary representation, then the number of such integers between L and R can be given by G(R) – G(L-1). This is when Digit DP (Dynamic Programming) comes into action. All such integer counting problems that satisfy the above property can be solved by the digit DP approach.
Intuition:
If we use the Digit DP approach to build all the binary String from the [ 0, R ] range and [0, L-1] range. then return Numbers in [0, R] range – Numbers in [0, L-1] range. So, we have only 2 digits to form the binary number i.e. 1 and 0.
Steps to solve the above approach:
- The algorithm iterates through each digit position of the binary representation of 10^9 i.e. it’s 32-bit long.
- It keeps track of the previous digit, whether it’s 0, 1, or an initial state
- It considers a “tight” flag that determines the upper bound of the current digit based on the previous digits and the given range.
- It recursively calculates the count of valid integers by considering all possible digits at each position, excluding combinations with consecutive 1s.
- The algorithm sums up the counts from all recursive calls and memoizes the result for future use.
- Finally, the algorithm returns the count of valid integers within the given range by subtracting the count of valid integers from the [L, R] range inclusively.
Below is the implementation of the above approach:
C++
// Cpp code for the above approach:#include <iostream>#include <cstring>#include <bitset>using namespace std;// Function to solve the digit DP problemlong long solve(string str, int idx, int prev, int tight, long long dp[33][3][2]);// Function to compute the count of non-negative integers// with no consecutive ones in their binary representationlong long digitDP(string str){ long long dp[33][3][2]; // 3D dynamic programming array memset(dp, -1, sizeof(dp)); // Initialize all elements to -1 return solve(str, 0, 2, 1, dp); // Solve the problem using dynamic programming}// Recursive function to solve the digit DP problemlong long solve(string str, int idx, int prev, int tight, long long dp[33][3][2]){ // Base case: If we have reached the end of the string, return 1 if (idx >= str.length()) { return 1LL; } // If the result for the current state is already computed, return it if (dp[idx][prev][tight] != -1) { return dp[idx][prev][tight]; } long long ans = 0; int upperBound = (tight == 1 ? str[idx] - '0' : 1); // Determine the upper bound for the current digit based on the "tight" flag // Iterate through all possible digits from 0 to the upper bound for (int dgt = 0; dgt <= upperBound; dgt++) { int newTight = (tight == 0 ? 0 : (dgt == upperBound ? 1 : 0)); // Determine the new "tight" flag based on the current digit and the upper bound // If the previous digit and the current digit are both 1, skip this combination if (prev == 1 && dgt == 1) { continue; } // Recursively solve for the next digit ans += solve(str, idx + 1, dgt, newTight, dp); } // Memoize the result and return it return dp[idx][prev][tight] = ans;}// Function to compute the count of non-negative integers// with no consecutive ones in their binary representationlong long findIntegers(int l, int r){ if (l == 0) { return digitDP(bitset<32>(r).to_string()); } l--; return digitDP(bitset<32>(r).to_string()) - digitDP(bitset<32>(l).to_string());}// Driver codeint main(){ // Example usage cout << findIntegers(0, 3) << endl; cout << findIntegers(5, 10) << endl; cout << findIntegers(10, 1000000000) << endl; return 0;} |
Java
// Java code for the above approach:import java.util.*;class GFG { public static long findIntegers(int l, int r) { // Convert the given integer to // its binary representation if (l == 0) { return digitDP(Integer.toBinaryString(r)); } l--; return digitDP(Integer.toBinaryString(r)) - digitDP(Integer.toBinaryString(l)); } public static long digitDP(String str) { // Create a 3D dynamic programming // array long[][][] dp = new long[33][3][2]; // Initialize all elements of // the array to -1 for (long[][] ar : dp) { for (long[] e : ar) { Arrays.fill(e, -1); } } // Solve the problem using // dynamic programming return solve(str, 0, 2, 1, dp); } public static long solve(String str, int idx, int prev, int tight, long[][][] dp) { // Base case: If we have reached // the end of the string, return 1 if (idx >= str.length()) { return 1L; } // If the result for the current // state is already computed, // return it if (dp[idx][prev][tight] != -1) { return dp[idx][prev][tight]; } long ans = 0; // Determine the upper bound for // the current digit based on // the "tight" flag int upperBound = (tight == 1 ? str.charAt(idx) - '0' : 1); // Iterate through all possible // digits from 0 to the upper bound for (int dgt = 0; dgt <= upperBound; dgt++) { // Determine the new "tight" // flag based on the current // digit and the upper bound int newTight = (tight == 0 ? 0 : (dgt == upperBound ? 1 : 0)); // If the previous digit and // the current digit are both 1, // skip this combination if (prev == 1 && dgt == 1) { continue; } // Recursively solve for // the next digit ans += solve(str, idx + 1, dgt, newTight, dp); } // Memoize the result and return it return dp[idx][prev][tight] = ans; } // Drivers code public static void main(String args[]) { System.out.println(findIntegers(0, 3)); System.out.println(findIntegers(5, 10)); System.out.println(findIntegers(10, 1000000000)); }} |
Python3
# Python3 code to solve the above problem# Function to solve the digit DP problemdef solve(str, idx, prev, tight, dp): # Base case: If we have reached the end of the string, return 1 if idx >= len(str): return 1 # If the result for the current state is already computed, return it if dp[idx][prev][tight] != -1: return dp[idx][prev][tight] ans = 0 upperBound = int(str[idx]) if tight == 1 else 1 # Determine the upper bound for the current digit based on the "tight" flag # Iterate through all possible digits from 0 to the upper bound for dgt in range(upperBound + 1): newTight = 0 if (tight == 0) else ( 1 if dgt == upperBound else 0 ) # Determine the new "tight" flag based on the current digit and the upper bound # If the previous digit and the current digit are both 1, skip this combination if prev == 1 and dgt == 1: continue # Recursively solve for the next digit ans += solve(str, idx + 1, dgt, newTight, dp) # Memoize the result and return it dp[idx][prev][tight] = ans return ans# Function to compute the count of non-negative integers# with no consecutive ones in their binary representationdef findIntegers(l, r): if l == 0: return solve(bin(r)[2:], 0, 2, 1, [[[-1 for _ in range(2)] for _ in range(3)] for _ in range(32)]) l -= 1 return solve(bin(r)[2:], 0, 2, 1, [[[-1 for _ in range(2)] for _ in range(3)] for _ in range(32)]) - solve(bin(l)[2:], 0, 2, 1, [[[-1 for _ in range(2)] for _ in range(3)] for _ in range(32)])# Example usageprint(findIntegers(0, 3))print(findIntegers(5, 10))print(findIntegers(10, 1000000000))# This code is contributed by Tapesh(tapeshdua420) |
C#
// C# code for the above approachusing System;public class GFG { public static long FindIntegers(int l, int r) { // Convert the given integer to its binary // representation if (l == 0) { return DigitDP(Convert.ToString(r, 2)); } l--; return DigitDP(Convert.ToString(r, 2)) - DigitDP(Convert.ToString(l, 2)); } public static long DigitDP(string str) { // Create a 3D dynamic programming array long[, , ] dp = new long[33, 3, 2]; // Initialize all elements of the array to -1 for (int i = 0; i < 33; i++) { for (int j = 0; j < 3; j++) { for (int k = 0; k < 2; k++) { dp[i, j, k] = -1; } } } // Solve the problem using dynamic programming return Solve(str, 0, 2, 1, dp); } public static long Solve(string str, int idx, int prev, int tight, long[, , ] dp) { // Base case: If we have reached the end of the // string, return 1 if (idx >= str.Length) { return 1L; } // If the result for the current state is already // computed, return it if (dp[idx, prev, tight] != -1) { return dp[idx, prev, tight]; } long ans = 0; // Determine the upper bound for the current digit // based on the "tight" flag int upperBound = (tight == 1) ? (str[idx] - '0') : 1; // Iterate through all possible digits from 0 to the // upper bound for (int dgt = 0; dgt <= upperBound; dgt++) { // Determine the new "tight" flag based on the // current digit and the upper bound int newTight = (tight == 0) ? 0 : ((dgt == upperBound) ? 1 : 0); // If the previous digit and the current digit // are both 1, skip this combination if (prev == 1 && dgt == 1) { continue; } // Recursively solve for the next digit ans += Solve(str, idx + 1, dgt, newTight, dp); } // Memoize the result and return it dp[idx, prev, tight] = ans; return ans; } // Driver code public static void Main(string[] args) { Console.WriteLine(FindIntegers(0, 3)); Console.WriteLine(FindIntegers(5, 10)); Console.WriteLine(FindIntegers(10, 1000000000)); }}// This code is contributed by Susobhan Akhuli |
Javascript
//JavaScript implementation of the above approach// Function to solve the digit DP problemfunction solve(str, idx, prev, tight, dp) { // Base case: If we have reached the end of the string, return 1 if (idx >= str.length) { return 1; } // If the result for the current state is already computed, return it if (dp[idx][prev][tight] !== -1) { return dp[idx][prev][tight]; } let ans = 0; let upperBound = tight === 1 ? parseInt(str[idx]) : 1; // Determine the upper bound for the current digit based on the "tight" flag // Iterate through all possible digits from 0 to the upper bound for (let dgt = 0; dgt <= upperBound; dgt++) { let newTight = tight === 0 ? 0 : (dgt === upperBound ? 1 : 0); // Determine the new "tight" flag based on the current digit and the upper bound // If the previous digit and the current digit are both 1, skip this combination if (prev === 1 && dgt === 1) { continue; } // Recursively solve for the next digit ans += solve(str, idx + 1, dgt, newTight, dp); } // Memoize the result and return it dp[idx][prev][tight] = ans; return ans;}// Function to compute the count of non-negative integers// with no consecutive ones in their binary representationfunction findIntegers(l, r) { if (l === 0) { return solve((r).toString(2), 0, 2, 1, Array.from({length: 32}, () => Array.from({length: 3}, () => Array.from({length: 2}, () => -1)))); } l -= 1; return solve((r).toString(2), 0, 2, 1, Array.from({length: 32}, () => Array.from({length: 3}, () => Array.from({length: 2}, () => -1)))) - solve((l).toString(2), 0, 2, 1, Array.from({length: 32}, () => Array.from({length: 3}, () => Array.from({length: 2}, () => -1))));}// Example usageconsole.log(findIntegers(0, 3));console.log(findIntegers(5, 10));console.log(findIntegers(10, 1000000000));// This code is contributed by Sakshi |
Output
3 4 2178302
Time Complexity: O(2*idx*prev*tight)
Auxiliary Space: O(idx * prev* tight)
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!
