0

Count numbers that does not contain digit N in given range

 4 weeks ago
source link: https://www.geeksforgeeks.org/count-numbers-that-does-not-contain-digit-n-in-given-range/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

Count numbers that does not contain digit N in given range

Last Updated : 13 Feb, 2023

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:

  • Python3
  • Javascript
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
// dp table initialized with -1
int dp[100001][2];
// Recursive Function to find numbers
// in the range L to R such that they
// do not contain digit N
int 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 N
int 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 Code
int 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;
}
Output 
9
81

Time Complexity: O(N), Where N is the number of digits to be filled
Auxiliary Space: O(N)

Related Articles:

"The DSA course helped me a lot in clearing the interview rounds. It was really very helpful in setting a strong foundation for my problem-solving skills. Really a great investment, the passion Sandeep sir has towards DSA/teaching is what made the huge difference." - Gaurav | Placed at Amazon

Before you move on to the world of development, master the fundamentals of DSA on which every advanced algorithm is built upon. Choose your preferred language and start learning today: 

DSA In JAVA/C++
DSA In Python
DSA In JavaScript
Trusted by Millions, Taught by One- Join the best DSA Course Today!

Recommended Problems
Frequently asked DSA Problems
Like Article
Suggest improvement
Share your thoughts in the comments

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK