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.
Input: digits =["1","3","5","7"], n =100Output: 20Explanation:
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.
Input: digits =["1","4","9"], n =1000000000Output: 29523Explanation:
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,thisis29523 integers that can be written using the digits array.
We count numbers less than or equal to n by considering two cases: numbers with fewer digits than n, and numbers with the same number of digits as n. For the latter, we use digit-by-digit DP, ensuring we do not exceed n at any position.
classSolution {
public:int atMostNGivenDigitSet(vector<string>& digits, int n) {
string s = to_string(n);
int k = s.size(), ans =0, D = digits.size();
for (int i =1; i < k; ++i) ans += pow(D, i);
for (int i =0; i < k; ++i) {
bool same = false;
for (auto& d : digits) {
if (d[0] < s[i]) ans += pow(D, k-i-1);
elseif (d[0] == s[i]) same = true;
}
if (!same) return ans;
}
return ans +1;
}
};
classSolution {
publicintatMostNGivenDigitSet(String[] digits, int n) {
String s = String.valueOf(n);
int k = s.length(), D = digits.length, ans = 0;
for (int i = 1; i < k; ++i) ans += Math.pow(D, i);
for (int i = 0; i < k; ++i) {
boolean same =false;
for (String d : digits) {
if (d.charAt(0) < s.charAt(i)) ans += Math.pow(D, k-i-1);
elseif (d.charAt(0) == s.charAt(i)) same =true;
}
if (!same) return ans;
}
return ans + 1;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
classSolution {
funatMostNGivenDigitSet(digits: Array<String>, n: Int): Int {
val s = n.toString()
val k = s.length
val D = digits.size
var ans = 0for (i in1 until k) ans +=Math.pow(D.toDouble(), i.toDouble()).toInt()
for (i in0 until k) {
var same = falsefor (d in digits) {
if (d[0] < s[i]) ans +=Math.pow(D.toDouble(), (k-i-1).toDouble()).toInt()
elseif (d[0] == s[i]) same = true }
if (!same) return ans
}
return ans + 1 }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
classSolution:
defatMostNGivenDigitSet(self, digits: list[str], n: int) -> int:
s = str(n)
k, D = len(s), len(digits)
ans =0for i in range(1, k):
ans += D ** i
for i in range(k):
same =Falsefor d in digits:
if d < s[i]:
ans += D ** (k-i-1)
elif d == s[i]:
same =Trueifnot same:
return ans
return ans +1
impl Solution {
pubfnat_most_n_given_digit_set(digits: Vec<String>, n: i32) -> i32 {
let s = n.to_string();
let k = s.len();
let d = digits.len();
letmut ans =0;
for i in1..k {
ans += d.pow(i asu32) asi32;
}
for (i, c) in s.chars().enumerate() {
letmut same =false;
for dd in&digits {
let dc = dd.chars().next().unwrap();
if dc < c {
ans += d.pow((k-i-1) asu32) asi32;
} elseif dc == c {
same =true;
}
}
if!same {
return ans;
}
}
ans +1 }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
classSolution {
atMostNGivenDigitSet(digits: string[], n: number):number {
consts=n.toString();
constk=s.length, D=digits.length;
letans=0;
for (leti=1; i<k; ++i) ans+= Math.pow(D, i);
for (leti=0; i<k; ++i) {
letsame=false;
for (constdofdigits) {
if (d<s[i]) ans+= Math.pow(D, k-i-1);
elseif (d===s[i]) same=true;
}
if (!same) returnans;
}
returnans+1;
}
}