What makes a number good in the Count Good Numbers problem?

A good number has even digits at even indices and prime digits (2,3,5,7) at odd indices.

How can I handle very large n without timing out?

Use modular exponentiation with recursion or iterative fast power methods to compute counts efficiently.

Why is modulo 10^9+7 needed?

The total count grows exponentially with n, so modulo prevents integer overflow and fits standard constraints.

Can I generate all good digit strings to count them?

No, generating strings is infeasible for large n; recognizing the pattern and using exponentiation is required.

What pattern does this problem illustrate?

It demonstrates a Math plus Recursion pattern, leveraging index-specific choices and modular exponentiation.

#1922

Medium

auto_awesome数学·递归

LeetCode 题解工作台

统计好数字的数目

我们称一个数字字符串是好数字当它满足（下标从 0 开始）偶数下标处的数字为偶数且奇数下标处的数字为质数（ 2 ， 3 ， 5 或 7 ）。比方说， "2582" 是好数字，因为偶数下标处的数字（ 2 和 8 ）是偶数且奇数下标处的数字（ 5 和 2 ）为质数。但 "3245" …

数学递归

题目描述

我们称一个数字字符串是 好数字 当它满足（下标从 0 开始）偶数下标处的数字为偶数且奇数下标处的数字为质数（2，3，5 或 7）。

比方说，"2582" 是好数字，因为偶数下标处的数字（2 和 8）是偶数且奇数下标处的数字（5 和 2）为质数。但 "3245" 不是好数字，因为 3 在偶数下标处但不是偶数。

给你一个整数 n ，请你返回长度为 n 且为好数字的数字字符串总数。由于答案可能会很大，请你将它对 10⁹ + 7 取余后返回 。

一个 数字字符串 是每一位都由 0 到 9 组成的字符串，且可能包含前导 0 。

示例 1：

输入：n = 1
输出：5
解释：长度为 1 的好数字包括 "0"，"2"，"4"，"6"，"8" 。

示例 2：

输入：n = 4
输出：400

示例 3：

输入：n = 50
输出：564908303

提示：

1 <= n <= 10¹⁵

lightbulb

解题思路

方法一：快速幂

长度为 $n$ 的好数字，偶数下标一共有 $\lceil \frac{n}{2} \rceil = \lfloor \frac{n + 1}{2} \rfloor$ 位，偶数下标可以填入 $5$ 种数字（ $0, 2, 4, 6, 8$ ）；奇数下标一共有 $\lfloor \frac{n}{2} \rfloor$ 位，奇数下标可以填入 $4$ 种数字（ $2, 3, 5, 7$ ）。因此长度为 $n$ 的好数字的个数为：

ans = 5^{\lceil \frac{n}{2} \rceil} \times 4^{\lfloor \frac{n}{2} \rfloor}

我们可以使用快速幂来计算 $5^{\lceil \frac{n}{2} \rceil}$ 和 $4^{\lfloor \frac{n}{2} \rfloor}$ ，时间复杂度为 $O(\log n)$ ，空间复杂度为 $O(1)$ 。

1

2

3

4

5

class Solution:
    def countGoodNumbers(self, n: int) -> int:
        mod = 10**9 + 7
        return pow(5, (n + 1) >> 1, mod) * pow(4, n >> 1, mod) % mod

speed

复杂度分析

指标	值
时间	complexity is O(log n) due to fast exponentiation recursion, and space complexity is O(1) since no additional arrays or recursion stacks grow with n.
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Check if candidate recognizes the even/prime index pattern immediately.
question_mark
Watch for attempts to generate all strings, which fails for large n.
question_mark
Listen for use of fast power recursion or modular arithmetic, signaling optimal approach.

warning

常见陷阱

外企场景

error
Trying to enumerate all strings leads to memory overflow or timeout.
error
Miscounting even vs odd positions when n is odd.
error
Neglecting modulo operation and causing integer overflow.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Change the set of prime digits or even digits to test adaptability of the power calculation.
arrow_right_alt
Ask for sum of digits of all good numbers instead of count, requiring extension of the pattern.
arrow_right_alt
Restrict digit strings to exclude leading zeros, modifying the first position choices.

help

常见问题

外企场景

继续练习

#1969 数组元素的最小非零乘积 #1823 找出游戏的获胜者 #1808 好因子的最大数目