Algorithm: Digit DP
Algorithm: Digit DP
The problem
is asking to find the count of integers in the range from 1 to K (inclusive)
such that the sum of digits is divisible by D.
Do you want
to exclude zeros?
If the
answer is yes than you need to track which states do not contain a nonzero
digit yet.
Why do I
want to exclude zeros, because 0 % 1 = 0 in python, so it says 0 is divisible
by 1 or actually any positive integer.
So we have
one part we will track which is the "zero"
Do you want
separate logic for tight bounds?
Yes you
want to make sure you have separate logic for when the prefix is exactly equal
to K. This way it doesn't allow any
numbers greater than K.
So we have
another part "tight"
Of course
we need to track at what index we are when iterating through the digits.
So we have
an "index"
But also
for this problem we need to track the remainder of the sum of digits for the
current state.
so we have
"rem"
So the dp
bags should be (index, rem, tight, zero)
Since K is
guaranteed to have at most 10,000 digits and D will have at most 100 possible
values. You can solve this in 10,000 x
100 x 10 x 2 x2 = 40,000,000 iterations.
That should be fast enough to solve the problem.
At the end
you are only interested in the states with rem = 0 and zero = 0 and you look at
the last index.
Runtime
Error
if you try
to read K and convert it to an int in python it will give RE. The reason is because it is an integer with 10,000
digits, it is way to large to store that on the computer. You have to read it in as a string.
Count the
good integers, which are integers that are divisible by their digit sum.
This is
trickier than the previous problem. And
it is asking something different.
Instead of asking if digit sum is divisible by some fixed integer. This is asking if integers are divisible by
their sum of digits.
If you do
the math on the input data, you can determine there will be between 1 to 126
for the digit sum, find the upper bound by taking 9 * 14. So what if you fix the digit sum does that
simplify the problem.
It does
because now you are just asking if the integer is divisible by that digit
sum.
So now you
just need to track for some fixed digit sum.
(index of
digit in original integer, current digit sum,
remainder modulo fixed digit sum, tight)
So how to
think of this you are packing all integers together that have a digit sum, and
possess this remainder modulo the fixed digit sum. Because those are all together right, if you
add the same digit to all integers in that state, they will all transition to
the same next state. And all will
transmit the remainder.
Another
proof is how this related to synthetic division.
As you can
see for each subinteger such as 5, 54, 543, 5432, ... You can know the
remainder when dividing by some digit sum, such as 7. And you get that is actually only value
needed for further calculation. That is
I can know that the final remainder = 0, because I knew the previous remainder
was 2. Just need (rem * 10 + dig) % ds
This
integer would not count actually because the digit sum exceeds 7, but it is
just an example of how the remainder works and why you can collect all integers
with the same remainder.
Why don't
you need to track zero this time? The
reason is because you will only add to the answer the values where the current
digit sum is equal to the fixed digit sum, so that will never happen if it has
just zeros.
126 * 126 *
126 * 2 * 10 = 40,007,520 iterations in
worst case. It is actually fewer than
that.
Count
the Number of Powerful Integers
This
problem gives you start, finish, limit and s.
The goal is to count the number of integers within the range [start,
finish] that contains the suffix s. But
no integer in the results can exceed the limit,
so you are not allowed to use any digits above the limit, and you are
guaranteed that the suffix s that is given will not contain any digits that
exceed the limit.
So we
identify this as digit dp, because the start and finish can be up to 10^15,
that is 15 digits.
So for this
problem I would say you have to track the following states.
You can
solve by taking dp(finish) - dp(start - 1), so let's look into what is the dp
solution.
You need
the following state (index of digit in integer, matches suffix s, tight)
2 * 15 * 2
* 2 * 10 = 1,200 iterations, seems
rather fast actually. But this should
work.
Notice we
don't care if it is all zeros, because that would by default not have a
matching suffix. Given s does not have
leading 0s.
One of the
tricky parts is dealing with the suffix logic of if it should be true or false,
because after the index in the current digit string has reached some value you
start comparing it to the suffix.
You just
have to perform some index math.
So given n1
= length of suffix, n2 = length of integer string
You know n2
>= n1 for it to be possible that they match.
when the
index i >= n2 - n1, it is time to compare them, because it is greater than
the difference, so you want to begin
comparing from left to right in the suffix string.
You can do
this with -(n2 - i), because it will be greater and decrease each time, it will
eventually reach n2 - i = 1 and so that is -1 which is the last element in the
suffix string. And it starts at the
front of the suffix string.
This
problem gives you strings of digits num1 and num2 which are the range in which
you want to count the number of good integers, [num1, num2]. Where the good integer is when the digit_sum
of integer is between min_sum and max_sum, [min_sum, max_sum]. Okay so we are going to be working with digit
sums again.
The
constraints are noteworthy, num2 <= 10^22 and max_sum <= 400
Everything
is an inclusive range.
Since it is
a range problem we solve with dp(num1) - dp(num2 - 1) again.
So for the
dp states, let's do something like this,
(index of
digit in string of digits, digit_sum, tight)
2 * 10 * 22
* 400 * 2 = 352,000 iterations, should be fast enough.
At the end
you just loop through min_sum to max_sum and return that summation of the final
dp states.
We don't
care about zero, cause the digit_sum has to be at least 1 anyway so there won't
be any only 0 integer that passes.
This is
quite similar to problems above just have to handle the [min_sum, max_sum]
range and know what it is that you want to return.
Number
of Beautiful Integers in the Range
This
problem is asking you to count the number of integers in a range [low, high]
where the integer is divisible by k and the number of odd and even digits are
equal.
low and
high <= 10^9, and k <= 20.
So what
would the states be for this one. Notice
this is similar to the problem above called digit sum divisible, the difference
is that what you are trying to divide by is just k
So you have
the states (index of digit in digit string, remainder modulo k, parity
count(even_cont - odd_count), tight, zero)
2 * 9 * 20
* 9 * 2 * 2 * 10 = 129,600 iterations, should be really fast.
Count
Stepping Numbers in Range
Similar to
above you have a range [low, high] in which you want to count the number of
stepping numbers, where a stepping number means that each adjacent digit has a
difference of exactly 1.
this time
low and high are <= 10^100.
So your dp
states (index of digit in digit string, last_dig, tight, zero)
2 * 100 *
10 * 10 * 2 * 2 = 80,000 iterations, so should be plenty fast enough.
Github
Repository: Code
Search for
the name of the problem to find the code for that specific problem.
Comments
Post a Comment