Count numbers that does not contain digit N in given range

0 0 11 minutes read

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 10⁹ + 7. ( L ? R ? 10^1000000)

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(18^N), 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 -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;
}

Java

// Java code to implement the approach
 
import 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 approach
MOD = 1e9 + 7;
 
# dp table initialized with -1
dp= [[-1]*(2) for _ in range(100001)];
 
# Recursive Function to find numbers
# in the range L to R such that they
# do not contain digit N
def 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 N
def 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 1
N = 5;
L = 1;
R = 10;
 
# Function Call
print(countInRange(N, L, R));
 
# Input 2
N1 = 5;
L1 = 1;
R1 = 100;
 
# Function Call
print(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 approach
 
let MOD = 1e9 + 7;
 
// dp table initialized with -1
let 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 N
function 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 N
function 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:

Introduction to Dynamic Programming – Data Structures and Algorithms Tutorials

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 zambiatek!