Given integers, N, L, and R, the task is to find the number of integers in the range L to R that does not contain the digit N. print the answer modulo 109 + 7. ( L ? R ? 101000000)
Examples:
Input: N = 5, L = 1, R = 10
Output: 9
Explanation: excluding all 5 others from 1 to 10 will be included in the answer.Input: N = 5, L = 1, R = 100
Output: 81
Explanation: Excluding 5, 15, 25, 35, 45, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 65, 75, 85, and 95 all numbers from 1 to 100 will be included in the answer
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(18N), Where N is the number of digits to be filled.
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] represents numbers in the range with i digits and j represents tight condition.
- 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 store the value of a state and whenever the function is called, return the stored value without computing again.
- First answer will be calculated for 0 to A – 1 and then calculated for 0 to B then latter one is subtracted with prior one to get answer for range [L, R]
Follow the steps below to solve the problem:
- Create a recursive function that takes two parameters i representing the position to be filled and j representing the tight condition.
- Call the recursive function for choosing all digits from 0 to 9 apart from N.
- Base case if size digit formed return 1;
- Create a 2d array dp[N][2] initially filled with -1.
- If the answer for a particular state is computed then save it in dp[i][j].
- If the answer for a particular state is already computed then just return dp[i][j].
Below is the implementation of the above approach:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;const int MOD = 1e9 + 7;// dp table initialized with -1int dp[100001][2];// Recursive Function to find numbers// in the range L to R such that they// do not contain digit Nint recur(int i, int j, int N, string& a){ // Base case if (i == a.size()) { return 1; } // If answer for current state is already // calculated then just return dp[i][j] if (dp[i][j] != -1) return dp[i][j]; // Answer initialized with zero int ans = 0; // Tight condition true if (j == 1) { // Iterating from 0 to max value // of tight condition cout<<((int)a[i] - 48)<<endl; for (int k = 0; k <= ((int)a[i] - 48); k++) { // N is not allowed to use if (k == N) continue; // When k is at max tight condition // remains even in next state if (k == ((int)a[i] - 48)) // Calling recursive function // for tight digit ans += recur(i + 1, 1, N, a); // Tight condition drops else // Calling recursive function // for digits less than tight // condition digit ans += recur(i + 1, 0, N, a); } } // Tight condition false else { // Iterating for all digits for (int k = 0; k <= 9; k++) { // Digit N is not possible if (k == N) continue; // Calling recursive function for // all digits from 0 to 9 ans += recur(i + 1, 0, N, a); } } // Save and return dp value return dp[i][j] = ans;}// Function to find numbers// in the range L to R such that they// do not contain digit Nint countInRange(int N, 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 sum of digits T from // 1 to L - 1 int ans1 = recur(0, 1, N, L); // Initializing dp array with - 1 memset(dp, -1, sizeof(dp)); // Numbers with sum of digits T in the // range 1 to R int ans2 = recur(0, 1, N, R); // Difference of ans2 and ans1 // will generate answer for required // range return ans2 - ans1;}// Driver Codeint main(){ // Input 1 int N = 5, L = 1, R = 10; // Function Call cout << countInRange(N, L, R) << endl; // Input 2 //int N1 = 5, L1 = 1, R1 = 100; // Function Call //cout << countInRange(N1, L1, R1) << endl; return 0;} |
Java
// Java code to implement the approachimport java.io.*;import java.util.*;class GFG { static final int MOD = 1_000_000_007; // dp table initialized with -1 static int[][] dp = new int[100001][2]; // Recursive Function to find numbers // in the range L to R such that they // do not contain digit N static int recur(int i, int j, int N, String a) { // Base case if (i == a.length()) { return 1; } // If answer for current state is already // calculated then just return dp[i][j] if (dp[i][j] != -1) return dp[i][j]; // Answer initialized with zero int ans = 0; // Tight condition true if (j == 1) { // Iterating from 0 to max value // of tight condition for (int k = 0; k <= a.charAt(i) - '0'; k++) { // N is not allowed to use if (k == N) continue; // When k is at max tight condition // remains even in next state if (k == a.charAt(i) - '0') // Calling recursive function // for tight digit ans += recur(i + 1, 1, N, a); // Tight condition drops else ans += recur(i + 1, 0, N, a); } } // Tight condition false else { // Iterating for all digits for (int k = 0; k <= 9; k++) { // Digit N is not possible if (k == N) continue; // Calling recursive function for // all digits from 0 to 9 ans += recur(i + 1, 0, N, a); } } // Save and return dp value return dp[i][j] = ans; } // Function to find numbers // in the range L to R such that they // do not contain digit N static int countInRange(int N, int A, int B) { // Initializing dp array with - 1 for (int[] row : dp) { Arrays.fill(row, -1); } A--; String L = Integer.toString(A); String R = Integer.toString(B); // Numbers with sum of digits T from // 1 to L - 1 int ans1 = recur(0, 1, N, L); // Initializing dp array with - 1 for (int[] row : dp) { Arrays.fill(row, -1); } // Numbers with sum of digits T in the // range 1 to R int ans2 = recur(0, 1, N, R); // Difference of ans2 and ans1 // will generate answer for required // range return ans2 - ans1; } public static void main(String[] args) { // Input 1 int N = 5; int L = 1; int R = 10; // Function Call System.out.println(countInRange(N, L, R)); // Input 2 int N1 = 5; int L1 = 1; int R1 = 100; // Function Call System.out.println(countInRange(N1, L1, R1)); }}// This contributed by lokeshmvs21. |
Python3
# Python code to implement the approachMOD = 1e9 + 7;# dp table initialized with -1dp= [[-1]*(2) for _ in range(100001)];# Recursive Function to find numbers# in the range L to R such that they# do not contain digit Ndef recur(i, j, N, a): # Base case if (i == len(a)) : return 1; # If answer for current state is already # calculated then just return dp[i][j] if (dp[i][j] != -1): return dp[i][j]; # Answer initialized with zero ans = 0; # Tight condition true if (j == 1) : # Iterating from 0 to max value # of tight condition for k in range(0, int(a[i])+1): # N is not allowed to use if (k == N): continue; # When k is at max tight condition # remains even in next state if (k == int(a[i])): # Calling recursive function # for tight digit ans += recur(i + 1, 1, N, a); # Tight condition drops else: # Calling recursive function # for digits less than tight # condition digit ans += recur(i + 1, 0, N, a); # Tight condition false else : # Iterating for all digits for k in range(0,10): # Digit N is not possible if (k == N): continue; # Calling recursive function for # all digits from 0 to 9 ans += recur(i + 1, 0, N, a); # Save and return dp value dp[i][j]=ans; return dp[i][j];# Function to find numbers# in the range L to R such that they# do not contain digit Ndef countInRange( N, A, B): # Initializing dp array with - 1 for i in range(0,100001): for j in range(0,2): dp[i][j]=-1; A -= 1; L = str(A); R = str(B); # Numbers with sum of digits T from # 1 to L - 1 ans1 = recur(0, 1, N, L); # Initializing dp array with - 1 for i in range(0,100001): for j in range(0,2): dp[i][j]=-1; # Numbers with sum of digits T in the # range 1 to R ans2 = recur(0, 1, N, R); # Difference of ans2 and ans1 # will generate answer for required # range return ans2 - ans1;# Driver Code# Input 1N = 5;L = 1;R = 10;# Function Callprint(countInRange(N, L, R));# Input 2N1 = 5;L1 = 1;R1 = 100;# Function Callprint(countInRange(N1, L1, R1));# This code is contributed by agrawalpooja976. |
C#
using System;namespace GFG{ static class Program { static readonly int MOD = 1_000_000_007; // dp table initialized with -1 static int[,] dp = new int[100001, 2]; // Recursive Function to find numbers // in the range L to R such that they // do not contain digit N static int Recur(int i, int j, int N, string a) { // Base case if (i == a.Length) { return 1; } // If answer for current state is already // calculated then just return dp[i][j] if (dp[i, j] != -1) return dp[i, j]; // Answer initialized with zero int ans = 0; // Tight condition true if (j == 1) { // Iterating from 0 to max value // of tight condition for (int k = 0; k <= a[i] - '0'; k++) { // N is not allowed to use if (k == N) continue; // When k is at max tight condition // remains even in next state if (k == a[i] - '0') // Calling recursive function // for tight digit ans += Recur(i + 1, 1, N, a); // Tight condition drops else ans += Recur(i + 1, 0, N, a); } } // Tight condition false else { // Iterating for all digits for (int k = 0; k <= 9; k++) { // Digit N is not possible if (k == N) continue; // Calling recursive function for // all digits from 0 to 9 ans += Recur(i + 1, 0, N, a); } } // Save and return dp value return dp[i, j] = ans; } // Function to find numbers // in the range L to R such that they // do not contain digit N static int CountInRange(int N, 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++) { dp[i, j] = -1; } } A--; string L = A.ToString(); string R = B.ToString(); // Numbers with sum of digits T from // 1 to L - 1 int ans1 = Recur(0, 1, N, L); // Initializing dp array with - 1 for (int i = 0; i < dp.GetLength(0); i++) { for (int j = 0; j < dp.GetLength(1); j++) { dp[i, j] = -1; } } // Numbers with sum of digits T in the // range 1 to R int ans2 = Recur(0, 1, N, R); // Difference of ans2 and ans1 // will generate answer for required // range return ans2 - ans1; } // Main Method static void Main(string[] args) { // Input 1 int N = 5; int L = 1; int R = 10; // Function Call Console.WriteLine(CountInRange(N, L, R)); // Input 2 int N1 = 5; int L1 = 1; int R1 = 100; // Function Call Console.WriteLine(CountInRange(N1, L1, R1)); } }}// This code is contributed by surajrasr7277 |
Javascript
// Javascript code to implement the approachlet MOD = 1e9 + 7;// dp table initialized with -1let dp = new Array(100001);for(let i=0; i<100001; i++) dp[i]= new Array(2);// Recursive Function to find numbers// in the range L to R such that they// do not contain digit Nfunction recur(i, j, N, a){ // Base case if (i == a.length) { return 1; } // If answer for current state is already // calculated then just return dp[i][j] if (dp[i][j] != -1) return dp[i][j]; // Answer initialized with zero let ans = 0; // Tight condition true if (j == 1) { // Iterating from 0 to max value // of tight condition for (let k = 0; k <= (parseInt(a[i])); k++) { // N is not allowed to use if (k == N) continue; // When k is at max tight condition // remains even in next state if (k == (parseInt(a[i]))) // Calling recursive function // for tight digit ans = ans + recur(i + 1, 1, N, a); // Tight condition drops else // Calling recursive function // for digits less than tight // condition digit ans = ans + recur(i + 1, 0, N, a); } } // Tight condition false else { // Iterating for all digits for (let k = 0; k <= 9; k++) { // Digit N is not possible if (k == N) continue; // Calling recursive function for // all digits from 0 to 9 ans += recur(i + 1, 0, N, a); } } // Save and return dp value return dp[i][j] = ans;}// Function to find numbers// in the range L to R such that they// do not contain digit Nfunction countInRange(N, A, B){ // Initializing dp array with - 1 for(let i=0; i<100001; i++) for(let j=0; j<2; j++) dp[i][j]=-1; A--; let L = A.toString(), R = B.toString(); // Numbers with sum of digits T from // 1 to L - 1 let ans1 = recur(0, 1, N, L); // Initializing dp array with - 1 for(let i=0; i<100001; i++) for(let j=0; j<2; j++) dp[i][j]=-1; // Numbers with sum of digits T in the // range 1 to R let ans2 = recur(0, 1, N, R); // Difference of ans2 and ans1 // will generate answer for required // range return ans2 - ans1;}// Driver Code // Input 1 let N = 5, L = 1, R = 10; // Function Call document.write(countInRange(N, L, R)); document.write("<br>"); // Input 2 let N1 = 5, L1 = 1, R1 = 100; // Function Call document.write(countInRange(N1, L1, R1)); |
Output
9 81
Time Complexity: O(N), Where N is the number of digits to be filled
Auxiliary Space: O(N)
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!
