 # DIGPRIME - Editorial

Prime Digits

Author, Tester, Editorialist: Dipen Ved

Under KJSCE CODECELL

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.