Round 1
Questions: Let us call a number "good" if no three consecutive digits form a prime number. For example, 1234 is "good", because 123 is not a prime number (divisible by 3), and 234 is not a prime number (divisible by 2). What is the sum of all 10000 digit good numbers modulo 1e9+7? (numbers with leading zeros are not allowed, for example 0123 is not a 4 digit number).
The sum of 3-digit "good" numbers is 419483.
The sum of 5-digit "good" numbers modulo 1e9+7 is 906471001.
Follow-up Question
- What approach did you consider for solving this problem?
Candidate's Approach
I thought of generating all numbers using some graph traversals, but couldn’t put it into code, let alone the optimality.
Interviewer's Feedback
No feedback provided.