Total count of sorted numbers up to N digits in the range [L, R]

Nishant Rana
Last Updated: May 13, 2022

Introduction:

We are given three integers N, L, and R. We need to find the count of the total sorted numbers each of up to N digits in the range [L, R].

 

Let us see a few examples:-

 

Input: N = 2, L = 3, R = 5

 

Output: 8

 

Explanation: 

We can form the following numbers:

Numbers of length 1: 3, 4, 5

Numbers of length 2: 33, 34, 44, 35, 45, 55

Hence count of the total sorted numbers formed are 3 + 6 = 9.

 

Input: N = 3, L = 5, R = 7

 

Output: 8

 

Explanation: 

We can form the following numbers:

Numbers of length 1: 5, 6, 7

Numbers of length 2: 55, 56, 57, 66, 67, 77

Numbers of length 3: 555, 556, 557, 566, 567, 577, 666, 667, 677, 777

Hence count of the total sorted numbers formed are 3 + 6 + 10 = 19.

 

Input: N = 5, L = 3, R = 9

 

Output: 791

 

Input: N = 6, L = 1, R = 9

 

Output: 5004

Approach:

Suppose N = 2, L = 3, R = 5

 

For N = 1: {3, 4, 5}

For N = 2: {33, 34, 35, 44, 45, 55}

 

From above we can see that for N = 2 all the numbers i.e. 3, 4, and 5 connected at the end of only those numbers which are smaller or equal to them. 

For example, 4 got connected to 3 and 4 only because these two numbers are only smaller and equal to 4.

 

From the above observation, we can say that we can use Dynamic Programming to solve this because we are using the answer of the previous state to find the answer of the current state.

 

Let us define the DP state:

DP[i][j]: It will store the count of the total sorted numbers f ‘i’ length numbers we can make using the digits from L to ‘j’.

 

How will we calculate the value of DP[i][j]?

DP[i][j] = DP[i-1][L] + DP[i-1][L+1] + ……. + DP[i-1][j]

 

We can optimize the above part by storing the prefix some for each row. This will eliminate the need to run a for loop to find the sum of DP[i-1][L] + … + DP[i-1][j].

Refer to the below implementation of the above approach.

 

class Main{
    
// Function to find count of the total sorted numbers
static int Count(int N, int L, int R)
{
    
    //Initializing the DP Array.
    int[][] dp = new int[N][R - L + 1];
    
    // Stores the result
    int ans = 0;
 
    // Traverse the range [0, N]
    for(int i = 0; i < N; i++)
    {
        dp[i][0] = 1;
    }
    
    // Traverse the range [1, R - L]
    for(int i = 1; i < dp[0].length; i++)
    {
        
        // Update dp[i][j]
        dp[0][i] = dp[0][i - 1] + 1;
    }
 
    // Assign dp[0][R-L] to ans
    ans = dp[0][R - L];
 
    // Traverse the range [1, N]
    for(int i = 1; i < N; i++)
    {
        
        // Traverse the range [1, R - L]
        for(int j = 1; j < dp[0].length; j++)
        {
            
            // Update dp[i][j]
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
 
        // Increment ans by dp[i-1][R-L]
        ans += dp[i][R - L];
    }
 
    // Return ans
    return ans;
}
 
public static void main(String args[])
{
    
    // Input
    int N = 3;
    int L = 6;
    int R = 9;
 
    // Function call
    System.out.println(Count(N, L, R));
}
}

 

Time Complexity: The time complexity for the above approach to find the count of the total sorted numbers is O(N * (R - L+ 1)) because we are running two Nested for loops of O(N) and O(R - L + 1) time. The outer for loop is running for O(N) time and for each iteration of the outer loop we are running the inner loop of O(R - L + 1) time.

 

Space Complexity: The space complexity for the above approach to find the count of the total sorted numbers is O(N * (R-L+1)) because we are initializing the DP table of size (N * (R-L+1)).

 

FAQs:

  1. What is the intuition behind the DP approach?
    • Suppose N = 2, L = 3, R = 5
      For N = 1: {3, 4, 5}
      For N = 2: {33, 34, 35, 44, 45, 55}
      From above we can see that for N = 2 all the numbers i.e. 3, 4, and 5 connected at the end of only those numbers which are smaller or equal to them. For example, 4 got connected to 3 and 4 only because these two numbers are only smaller and equal to 4.
      From the above observation, we can say that we can use Dynamic Programming to solve this because we are using the answer of the previous state to find the answer of the current state.
  2. What does DP[i][j] store?
    • DP[i][j] will store the count of the total sorted numbers f ‘i’ length numbers we can make using the digits from L to ‘j’.
  3. What is the time complexity for the approach used to find the count of the total sorted numbers?
    • The time complexity for the above approach is O(N * (R-L+1)) because we are running two Nested for loops of O(N) and O(R-L+1) time.

 

Key Takeaways: 

In this blog, we have covered the following things:

  1. We first discussed the approach to find the count of the total sorted numbers up to N digits in the range [L, R].
  2. Then we saw how to implement the approach discussed.

 

If you want to learn more about Dynamic Programming and want to practice some questions which require you to take your basic knowledge on Dynamic Programming a notch higher, then you can visit our Guided Path for Dynamic Programming

 

Until then, All the best for your future endeavors, and Keep Coding.








 

Was this article helpful ?
1 upvote