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)).
250+ registered 
