### PROBLEM LINK:

Prime Digits

**Author, Tester, Editorialist:** Dipen Ved

Under KJSCE CODECELL

### DIFFICULTY:

MEDIUM-HARD.

### PREREQUISITES:

Dynamic Programming and Combinatorics

### PROBLEM:

Given a number N, you have to find the number of numbers less than or equal to N such that each number has atleast one prime digit in it.

### QUICK EXPLANATION:

Thinking about the question, we need to decide states. I depends on 3 states. Since N goes to 10^18, an optimized DP is needed.

### EXPLANATION:

Lets discuss down the fast top down approach for the question.

Thinking about the question, we need to decide states

I’ll denote my states by -

- idx -> which position I am on the current number.
- tight -> If I can use all the 0-9 digits at this current idx or not. I will only be able to use all the 0-9 digits if I have previously used a digit which was less than any of the previous s[i]'s for all i < idx
- flag -> If I have encountered any kind of prime digit before. A less optimized solution.

So my Recursion goes like

```
F(idx, tight, flag)
```

Base case will be if you reach idx as n and your flag is set, then you have found 1 way and return 1 else 0

Rest is just simple recursion!

There can be one more optimization in case you have flag set to 1 and tight set to 0, which is infact a good situation.

### AUTHOR’S AND TESTER’S SOLUTIONS:

Solution can be found here.