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.