DIGPRIME - Editorial

PROBLEM LINK:

Prime Digits

Practice
Contest

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.