### 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 ^{K}C_{1} + ^{K}C_{2} + ^{K}C_{3} + ^{K}C_{4}.

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 **A _{1}** occurences of 1,

**A**occurences of 7

_{7}and

**A**occurences of 9. Then number of ways we can choose a sub-sequence where

_{9}these 4 digits are chosen is :

A

^{A1}C_{2}*A

_{7}* A_{9}```
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.