Problem
We have a sorted set of digits D
, a non-empty subset of {'1','2','3','4','5','6','7','8','9'}
. (Note that '0'
is not included.)
Now, we write numbers using these digits, using each digit as many times as we want. For example, if D = {'1','3','5'}
, we may write numbers such as '13', '551', '1351315'
.
Return the number of positive integers that can be written (using the digits of D
) that are less than or equal to N
.
Example 1:
Input: D = ["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: D = ["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 of D.
Note:
D
is a subset of digits'1'-'9'
in sorted order.1 <= N <= 10^9
Solution -1: DFS (TLE)
Time complexity: O(|D|^log10(N))
Space complexity: O(n)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
// Author: Huahua class Solution { public: int atMostNGivenDigitSet(vector<string>& D, int N) { int ans = 0; dfs(D, 0, N, ans); return ans; } private: void dfs(const vector<string>& D, int cur, int N, int& ans) { if (cur > N) return; if (cur > 0 && cur <= N) ++ans; for (const string& d : D) dfs(D, cur * 10 + d[0] - '0', N, ans); } }; |
Solution 1: Math
Time complexity: O(log10(N))
Space complexity: O(1)
Suppose N has n digits.
less than n digits
We can use all the numbers from D to construct numbers of with length 1,2,…,n-1 which are guaranteed to be less than N.
e.g. n = 52125, D = [1, 2, 5]
format X: e.g. 1, 2, 5 counts = |D| ^ 1
format XX: e.g. 11,12,15,21,22,25,51,52,55, counts = |D|^2
format XXX: counts = |D|^3
format XXXX: counts = |D|^4
exact n digits
if all numbers in D != N[0], counts = |d < N[0] | d in D| * |D|^(n-1), and we are done.
e.g. N = 34567, D = [1,2,8]
we can make:
- X |3|^1
- XX |3| ^ 2
- XXX |3| ^ 3
- XXXX |3| ^ 3
- 1XXXX, |3|^4
- 2XXXX, |3|^4
- we can’t do 8XXXX
Total = (3^1 + 3^2 + 3^3 + 3^4) + 2 * |3|^ 4 = 120 + 162 = 282
N = 52525, D = [1,2,5]
However, if d = N[i], we need to check the next digit…
- X |3|^1
- XX |3| ^ 2
- XXX |3| ^ 3
- XXXX |3| ^ 3
- 1XXXX, |3|^4
- 2XXXX, |3|^4
- 5????
- 51XXX |3|^3
- 52???
- 521XX |3|^2
- 522XX |3|^2
- 525??
- 5251X |3|^1
- 5252?
- 52521 |3|^0
- 52522 |3|^0
- 52525 +1
total = (120) + 2 * |3|^4 + |3|^3 + 2*|3|^2 + |3|^1 + 2 * |3|^0 + 1 = 120 + 213 = 333
if every digit of N is from D, then we also have a valid solution, thus need to + 1.
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
class Solution { public: int atMostNGivenDigitSet(vector<string>& D, int N) { const string s = to_string(N); const int n = s.length(); int ans = 0; for (int i = 1; i < n; ++i) ans += pow(D.size(), i); for (int i = 0; i < n; ++i) { bool prefix = false; for (const string& d : D) { if (d[0] < s[i]) { ans += pow(D.size(), n - i - 1); } else if (d[0] == s[i]) { prefix = true; break; } } if (!prefix) return ans; } // plus one for solution N itself, all the digits are from D. return ans + 1; } }; |
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
// Author: Huahua, 4 ms class Solution { public int atMostNGivenDigitSet(String[] D, int N) { char[] s = String.valueOf(N).toCharArray(); int n = s.length; int ans = 0; for (int i = 1; i < n; ++i) ans += (int)Math.pow(D.length, i); for (int i = 0; i < n; ++i) { boolean prefix = false; for (String d : D) { if (d.charAt(0) < s[i]) { ans += Math.pow(D.length, n - i - 1); } else if (d.charAt(0) == s[i]) { prefix = true; break; } } if (!prefix) return ans; } return ans + 1; } } |
Python3
1 2 3 4 5 6 7 8 9 10 |
# Author: Huahua, 36 ms class Solution: def atMostNGivenDigitSet(self, D, N): s = str(N) n = len(s) ans = sum(len(D) ** i for i in range(1, n)) for i, c in enumerate(s): ans += len(D) ** (n - i - 1) * sum(d < c for d in D) if c not in D: return ans return ans + 1 |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment