Special Digit Numbers

Hard

0/120

0 upvote

Asked in company

Problem statement

You are given three integers: d, e, and f. Your task is to count the number of special d-digit numbers that satisfy a specific condition.

A d-digit number is considered special based on the digits allowed at each position (1-indexed, from left to right):

  If a digit's position k is a prime number (2, 3, 5, 7, ...), the digit at that position must be one of {2, 3, 5, 7}.

  If a digit's position k is not a prime number (1, 4, 6, 8, ...), the digit at that position must be one of {0, 1, 4, 6, 8, 9}.

Additionally, a valid d-digit number cannot have a leading zero.

The condition to satisfy is that when the special d-digit number is taken modulo e, the remainder must be exactly f.

You need to return the total count of such numbers, with the final answer taken modulo 10^9 + 7.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first and only line of input contains three space-separated integers: d, e, and f.

Output Format:

Print a single integer representing the total count of such special numbers, modulo 10^9 + 7.

Note:

This problem is best solved using Dynamic Programming. A state dp[i][j] can represent the number of ways to form an i-digit special number prefix that results in a remainder of j when taken modulo e. You will need an efficient way to check for primality, such as a Sieve of Eratosthenes, pre-computed for all positions up to d.

Sample Input 1:

2 3 0

Sample Output 1:

Explanation for Sample 1:

Pos 1 (not prime): {1,4,6,8,9}. Pos 2 (prime): {2,3,5,7}.
Numbers:
  1x: 12, 13, 15, 17 -> 12%3=0, 15%3=0. (2 ways)
  4x: 42, 43, 45, 47 -> 42%3=0, 45%3=0. (2 ways)
  6x: 62, 63, 65, 67 -> 63%3=0. (1 way)
  8x: 82, 83, 85, 87 -> 87%3=0. (1 way)
  9x: 92, 93, 95, 97 -> 93%3=0. (1 way)
Total ways = 2+2+1+1+1 = 7.

Expected Time Complexity:

The expected time complexity is O(N^3).

Constraints:

1 <= d <= 1000
1 <= e <= 100
0 <= f < e

Time limit: 1 sec

Approaches (1)

Approach 1

Time Complexity

Space Complexity

(100% EXP penalty)

Special Digit Numbers

Console