Solution
Approach 1: Dynamic Programming + Counting
Intuition
First, call a positive integer X
valid if X <= N
and X
only consists of digits from D
. Our goal is to find the number of valid integers.
Say N
has K
digits. If we write a valid number with k
digits (k < K
), then there are possible numbers we could write, since all of them will definitely be less than N
.
Now, say we are to write a valid K
digit number from left to right. For example, N = 2345
, K = 4
, and D = '1', '2', ..., '9'
. Let's consider what happens when we write the first digit.
-
If the first digit we write is less than the first digit of
N
, then we could write any numbers after, for a total of valid numbers from this one-digit prefix. In our example, if we start with1
, we could write any of the numbers1111
to1999
from this prefix. -
If the first digit we write is the same, then we require that the next digit we write is equal to or lower than the next digit in
N
. In our example (withN = 2345
), if we start with2
, the next digit we write must be3
or less. -
We can't write a larger digit, because if we started with eg.
3
, then even a number of3000
is definitely larger thanN
.
Algorithm
Let dp[i]
be the number of ways to write a valid number if N
became N[i], N[i+1], ...
. For example, if N = 2345
, then dp[0]
would be the number of valid numbers at most 2345
, dp[1]
would be the ones at most 345
, dp[2]
would be the ones at most 45
, and dp[3]
would be the ones at most 5
.
Then, by our reasoning above, dp[i] = (number of d in D with d < S[i]) * ((D.length) ** (K-i-1))
, plus dp[i+1]
if S[i]
is in D
.
Complexity Analysis
-
Time Complexity: , and assuming is constant. (We could make this better by pre-calculating the number of
d < S[i]
for all possible digitsS[i]
, but this isn't necessary.) -
Space Complexity: , the space used by
S
anddp
. (Actually, we could store only the last 2 entries ofdp
, but this isn't necessary.)
Approach 2: Mathematical
Intuition
As in Approach #1, call a positive integer X
valid if X <= N
and X
only consists of digits from D
.
Now let B = D.length
. There is a bijection between valid integers and so called "bijective-base-B
" numbers. For example, if D = ['1', '3', '5', '7']
, then we could write the numbers '1', '3', '5', '7', '11', '13', '15', '17', '31', ...
as (bijective-base-B
) numbers '1', '2', '3', '4', '11', '12', '13', '14', '21', ...
.
It is clear that both of these sequences are increasing, which means that the first sequence is a contiguous block of valid numbers, followed by invalid numbers.
Our approach is to find the largest valid integer, and convert it into bijective-base-B
from which it is easy to find its rank (position in the sequence.) Because of the bijection, the rank of this element must be the number of valid integers.
Continuing our example, if N = 64
, then the valid numbers are '1', '3', ..., '55', '57'
, which can be written as bijective-base-4 numbers '1', '2', ..., '33', '34'
. Converting this last entry '34'
to decimal, the answer is 16
(3 * 4 + 4).
Algorithm
Let's convert N
into the largest possible valid integer X
, convert X
to bijective-base-B, then convert that result to a decimal answer. The last two conversions are relatively straightforward, so let's focus on the first part of the task.
Let's try to write X
one digit at a time. Let's walk through an example where D = ['2', '4', '6', '8']
. There are some cases:
-
If the first digit of
N
is inD
, we write that digit and continue. For example, ifN = 25123
, then we will write2
and continue. -
If the first digit of
N
is larger thanmin(D)
, then we write the largest possible number fromD
less than that digit, and the rest of the numbers will be big. For example, ifN = 5123
, then we will write4888
(4
then888
). -
If the first digit of
N
is smaller thanmin(D)
, then we must "subtract 1" (in terms ofX
's bijective-base-B representation), and the rest of the numbers will be big.For example, if
N = 123
, we will write88
. IfN = 4123
, we will write2888
. And ifN = 22123
, we will write8888
. This is because "subtracting 1" from'', '4', '22'
yields'', '2', '8'
(can't go below 0).
Actually, in our solution, it is easier to write in bijective-base-B, so instead of writing digits of D
, we'll write the index of those digits (1-indexed). For example, X = 24888
will be A = [1, 2, 4, 4, 4]
. Afterwards, we convert this to decimal.
Complexity Analysis
-
Time Complexity: , and assuming is constant.
-
Space Complexity: , the space used by
A
.
Analysis written by: @awice.