PROBLEM LINK:
DIFFICULTY:
Easy
PREREQUISITES:
DP, Basic number theory
PROBLEM:
A number is lucky if after repeated addition of digits, we get 9. Given a sequence of digits, task is to find out how many of its sub-sequences of length between 1 to 4 are lucky numbers.
QUICK EXPLANATION:
A number N is lucky iff N > 0 and N % 9 = 0. So here lucky sub-sequences are those 1-4 digit sub-sequences whose sum is 9, 18, 27 or 36. We can find this either using DP or some combinatorial arguments.
DETAILED EXPLANATION:
Repeated digital sum of a number is also called digital root of the number. It can be shown that digital root of a number N is N % 9. For a proof of this and other interesting facts about digital root, you can read its wikipedia page.
Now those numbers are lucky whose digital root is 9. All these numbers would be multiples of 9. Let’s see a DP solution first. Let dp[i][j][k] denote the number of ways of choosing k digits from the left most i digits of the sequence such that the sum of chosen numbers is j modulo 9. We finally need sum over k from 1 to 4 : dp[L][0][k], though we’d need to remove those cases where the produced number is a zero. How to find the number of those cases? Let there be K 0 digits in sequence. Any 1-4 of these give us a number which is 0 so we can subtract KC1 + KC2 + KC3 + KC4.
What is the recurrence for the DP? For every digit, we’ve two choices - whether to include it or not include it. So we can frame recurrence easily as follows :
dp[i][j][k] = dp[i-1][j][k] + dp[i-1][j'][k-1] where j' is such that j' + S[i] = j (mod 9)
This method takes around O(length * 10 * 4) and might be a little too slow to clear the time limits.
There is an alternative method as well. Assume that number is 4 digits long. We
could move over all 4 digit numbers, see if sum of their digits is one of 9, 18, 27, 36
or not. If yes, we could find out in how many ways can we choose this 4 digit
number as subsequence from the given sequence. But it is not so easy to find out
this number quickly.
But hope is not lost! Note that order of digits is not
important for finding sum of digits. So we could as well move over all 4 digits
(producing each combination exactly once) and see how many times we can choose
such digits. For an example let’s say that we choose {1, 1, 7, 9} to be our
digit set. Further say our sequence has A1 occurences of 1,
A7 occurences of 7
and A9 occurences of 9. Then number of ways we can choose a sub-sequence where
these 4 digits are chosen is : A1C2 *
A7 * A9
ans = 0
for a from 0 to 9:
for b from a to 9
for c from b to 9:
for d from c to 9:
sum = a + b + c + d
if(sum > 0 and sum % 9 == 0)
fill(used_count, 0)
used_count[a] ++
used_count[b] ++
used_count[c] ++
used_count[d] ++
its = 1
for i in 0 to 9:
its *= (total[i] choose used_count[i])
ans += its
We can similarly write loops for the cases when number of digits is 3, 2, or 1.
Look at tester’s solution for a smart implementation where he hasn’t written
different loops for 3, 2 or 1 digits.
SETTER’S SOLUTION:
To be uploaded soon.
TESTER’S SOLUTION:
Can be found here.
