| comments | difficulty | edit_url | tags | |||||
|---|---|---|---|---|---|---|---|---|
true |
Hard |
|
Given an array of digits which is sorted in non-decreasing order. You can write numbers using each digits[i] as many times as we want. For example, if digits = ['1','3','5'], we may write numbers such as '13', '551', and '1351315'.
Return the number of positive integers that can be generated that are less than or equal to a given integer n.
Example 1:
Input: digits = ["1","3","5","7"], n = 100 Output: 20 Explanation: The 20 numbers that can be written are: 1, 3, 5, 7, 11, 13, 15, 17, 31, 33, 35, 37, 51, 53, 55, 57, 71, 73, 75, 77.
Example 2:
Input: digits = ["1","4","9"], n = 1000000000 Output: 29523 Explanation: We can write 3 one digit numbers, 9 two digit numbers, 27 three digit numbers, 81 four digit numbers, 243 five digit numbers, 729 six digit numbers, 2187 seven digit numbers, 6561 eight digit numbers, and 19683 nine digit numbers. In total, this is 29523 integers that can be written using the digits array.
Example 3:
Input: digits = ["7"], n = 8 Output: 1
Constraints:
1 <= digits.length <= 9digits[i].length == 1digits[i]is a digit from'1'to'9'.- All the values in
digitsare unique. digitsis sorted in non-decreasing order.1 <= n <= 109
This problem essentially asks for the number of positive integers that can be generated from the digits in digits within the given range
For the range
However, for this problem, we only need to find the value for the range
Here, we use memoization to implement Digit DP. We start searching from the top, get the number of solutions at the bottom, and return the answers layer by layer until we get the final answer from the starting point.
The basic steps are as follows:
We convert the number
Next, we design a function
- The integer
$i$ represents the current position in the string$s$ . - The boolean
$\textit{lead}$ indicates whether the current number contains only leading zeros. - The boolean
$\textit{limit}$ indicates whether the current position is restricted by the upper bound.
The function executes as follows:
If
Otherwise, we calculate the upper bound
Then, we enumerate the current digit
Finally, we return
The time complexity is
Similar problems:
- 233. Number of Digit One
- 357. Count Numbers with Unique Digits
- 600. Non-negative Integers without Consecutive Ones
- 788. Rotated Digits
- 1012. Numbers With Repeated Digits
- 2376. Count Special Integers
class Solution:
def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:
@cache
def dfs(i: int, lead: int, limit: bool) -> int:
if i >= len(s):
return lead ^ 1
up = int(s[i]) if limit else 9
ans = 0
for j in range(up + 1):
if j == 0 and lead:
ans += dfs(i + 1, 1, limit and j == up)
elif j in nums:
ans += dfs(i + 1, 0, limit and j == up)
return ans
s = str(n)
nums = {int(x) for x in digits}
return dfs(0, 1, True)class Solution {
private Set<Integer> nums = new HashSet<>();
private char[] s;
private Integer[] f;
public int atMostNGivenDigitSet(String[] digits, int n) {
s = String.valueOf(n).toCharArray();
f = new Integer[s.length];
for (var x : digits) {
nums.add(Integer.parseInt(x));
}
return dfs(0, true, true);
}
private int dfs(int i, boolean lead, boolean limit) {
if (i >= s.length) {
return lead ? 0 : 1;
}
if (!lead && !limit && f[i] != null) {
return f[i];
}
int up = limit ? s[i] - '0' : 9;
int ans = 0;
for (int j = 0; j <= up; ++j) {
if (j == 0 && lead) {
ans += dfs(i + 1, true, limit && j == up);
} else if (nums.contains(j)) {
ans += dfs(i + 1, false, limit && j == up);
}
}
if (!lead && !limit) {
f[i] = ans;
}
return ans;
}
}class Solution {
public:
int atMostNGivenDigitSet(vector<string>& digits, int n) {
string s = to_string(n);
unordered_set<int> nums;
for (auto& x : digits) {
nums.insert(stoi(x));
}
int m = s.size();
int f[m];
memset(f, -1, sizeof(f));
auto dfs = [&](auto&& dfs, int i, bool lead, bool limit) -> int {
if (i >= m) {
return lead ? 0 : 1;
}
if (!lead && !limit && f[i] != -1) {
return f[i];
}
int up = limit ? s[i] - '0' : 9;
int ans = 0;
for (int j = 0; j <= up; ++j) {
if (j == 0 && lead) {
ans += dfs(dfs, i + 1, true, limit && j == up);
} else if (nums.count(j)) {
ans += dfs(dfs, i + 1, false, limit && j == up);
}
}
if (!lead && !limit) {
f[i] = ans;
}
return ans;
};
return dfs(dfs, 0, true, true);
}
};func atMostNGivenDigitSet(digits []string, n int) int {
s := strconv.Itoa(n)
m := len(s)
f := make([]int, m)
for i := range f {
f[i] = -1
}
nums := map[int]bool{}
for _, d := range digits {
x, _ := strconv.Atoi(d)
nums[x] = true
}
var dfs func(i int, lead, limit bool) int
dfs = func(i int, lead, limit bool) int {
if i >= m {
if lead {
return 0
}
return 1
}
if !lead && !limit && f[i] != -1 {
return f[i]
}
up := 9
if limit {
up = int(s[i] - '0')
}
ans := 0
for j := 0; j <= up; j++ {
if j == 0 && lead {
ans += dfs(i+1, true, limit && j == up)
} else if nums[j] {
ans += dfs(i+1, false, limit && j == up)
}
}
if !lead && !limit {
f[i] = ans
}
return ans
}
return dfs(0, true, true)
}function atMostNGivenDigitSet(digits: string[], n: number): number {
const s = n.toString();
const m = s.length;
const f: number[] = Array(m).fill(-1);
const nums = new Set<number>(digits.map(d => parseInt(d)));
const dfs = (i: number, lead: boolean, limit: boolean): number => {
if (i >= m) {
return lead ? 0 : 1;
}
if (!lead && !limit && f[i] !== -1) {
return f[i];
}
const up = limit ? +s[i] : 9;
let ans = 0;
for (let j = 0; j <= up; ++j) {
if (!j && lead) {
ans += dfs(i + 1, true, limit && j === up);
} else if (nums.has(j)) {
ans += dfs(i + 1, false, limit && j === up);
}
}
if (!lead && !limit) {
f[i] = ans;
}
return ans;
};
return dfs(0, true, true);
}