Count Good Numbers
Get a Strong Hold DSA practice problem on Onlearn.
Difficulty: easy.
Topics: Count Good numbers, Mathematical Algorithms, Modular Exponentiation, Time Complexity, Space Complexity, Big O Notation, Combinatorics, Input/Output Operations, Data Types, constraints, dynamic programming, counting, mathematical operations, recursion, number theory, Number Manipulation, Prime Numbers.
Count Good Numbers You are given an integer n. A number is considered "good" if its digits at even indices (0 indexed) are even (0, 2, 4, 6, 8) and its digits at odd indices (0 indexed) are prime (2, 3, 5, 7). Return the number of "good" numbers of length n. Since the answer can be very large, return it modulo 10^9 + 7. Input Specification The sole input is an integer n. Output Specification Return a single integer, the count of good numbers of length n, modulo 10^9 + 7. Constraints 1 <= n <= 10^18 Sample Test Cases Sample 1: Input: n = 1 Output: 5 Explanation: For n = 1, the only index is 0 (even). The digits at even indices must be even (0, 2, 4, 6, 8). There are 5 such digits. So, the good numbers are 0, 2, 4, 6, 8. Sample 2: Input: n = 2 Output: 20 Explanation: For n = 2, index 0 is even and index 1 is odd. Digits at index 0 (even) can be (0, 2, 4, 6, 8) 5 choices. Digits at index 1 (odd) can be (2, 3, 5, 7) 4 choices. Total good numbers = 5 4 = 20. Sample 3: Input: n = 3 Output: 100 Explanation: For n = 3, indices are 0 (even), 1 (odd), 2 (even). Digits at index 0 (even) 5 choices. Digits at index 1 (odd) 4 choices. Digits at index 2 (even) 5 choices. Total good numbers = 5 4 5 = 100.