LeetCode 3519: Count Numbers with Non-Decreasing Digits Solution
Master LeetCode problem 3519 (Count Numbers with Non-Decreasing Digits ), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.
3519. Count Numbers with Non-Decreasing Digits
Problem Explanation
Explanation:
To solve this problem, we can use dynamic programming. We need to count the numbers with non-decreasing digits in the range [l, r] when represented in base b. We can create a 3D dynamic programming array dp[num of digits][num of digits][b] to store the count of numbers with non-decreasing digits up to a certain digit position.
- Initialize the dp array with zeros.
- Calculate the count of numbers with non-decreasing digits starting from each digit and update the dp array accordingly.
- Finally, sum up the counts from dp[l.length()][num of digits][b] to dp[r.length()][num of digits][b] to get the total count.
Time complexity: O(n * n * b) where n is the length of the strings l and r. Space complexity: O(n * n * b).
:
Solution Code
class Solution {
public int countNonDecreasing(String l, String r, int b) {
int mod = 1000000007;
int[][][] dp = new int[101][101][11];
for (int i = 0; i <= 9; i++) {
dp[1][1][i] = 1;
}
for (int i = 2; i <= 100; i++) {
for (int j = 1; j <= i; j++) {
for (int k = 0; k < b; k++) {
for (int p = 0; p <= k; p++) {
dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j - 1][p]) % mod;
}
}
}
}
int res = 0;
int lenR = r.length();
for (int i = 1; i < lenR; i++) {
for (int j = 1; j <= i; j++) {
for (int k = 1; k < b; k++) {
res = (res + dp[i][j][k]) % mod;
}
}
}
return res;
}
}Try It Yourself
Loading code editor...
Related LeetCode Problems
Frequently Asked Questions
How to solve LeetCode 3519 (Count Numbers with Non-Decreasing Digits )?
This page provides optimized solutions for LeetCode problem 3519 (Count Numbers with Non-Decreasing Digits ) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.
What is the time complexity of LeetCode 3519 (Count Numbers with Non-Decreasing Digits )?
The time complexity for LeetCode 3519 (Count Numbers with Non-Decreasing Digits ) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.
Can I run code for LeetCode 3519 on DevExCode?
Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 3519 in Java, C++, or Python.