Page Contents
Count Good Numbers
A digit string is good if the digits (0-indexed) at even indices are even and the digits at odd indices are prime (2
, 3
, 5
, or 7
).
See Also: Weekly Contest 248
- For example,
"2582"
is good because the digits (2
and8
) at even positions are even and the digits (5
and2
) at odd positions are prime. However,"3245"
is not good because3
is at an even index but is not even.
Given an integer n
, return the total number of good digit strings of length n
. Since the answer may be large, return it modulo 109 + 7
.
A digit string is a string consisting of digits 0
through 9
that may contain leading zeros.
Example 1:
Input: n = 1 Output: 5 Explanation: The good numbers of length 1 are "0", "2", "4", "6", "8".
Example 2:
Input: n = 4 Output: 400
Example 3:
Input: n = 50 Output: 564908303
Constraints:
1 <= n <= 1015
Solution
Program C++
class Solution {
public:
const long long MOD = 1000000007;
long long mul(long long a, long long x, long long p)
{
if (x == 0) return 1;
long long res = mul(a,x/2,p);
res = res * res % p;
if (x%2)
res = res * a % p;
return res;
}
int countGoodNumbers(long long n) {
long long pe = n/2 + n%2, po = (n/2);
return mul(5,pe,MOD) * mul(4,po,MOD) % MOD;
}
};
Program Python
class Solution:
def countGoodNumbers(self, n: int) -> int:
mod = 10 ** 9 + 7
return pow(5, (n + 1) // 2, mod) * pow(4, n // 2, mod) % mod
Program Java
Credit: Here
- For each even index, there are 5 options:
0
,2
,4
,6
,8
; - For each odd index, there are 4 options:
2
,3
,5
,7
; - If
n
is even, the solution is(4 * 5) ^ (n / 2)
; if odd,(4 * 5) ^ (n / 2) * 5
.
public int countGoodNumbers(long n) {
long good = n % 2 == 0 ? 1 : 5;
long x = 4 * 5;
for (long i = n / 2; i > 0; i /= 2, x = x * x % 1_000_000_007) {
if (i % 2 != 0) {
good = good * x % 1_000_000_007;
}
}
return (int)good;
}
def countGoodNumbers(self, n: int) -> int:
good, x, i = 5 ** (n % 2), 4 * 5, n // 2
while i > 0:
if i % 2 == 1:
good = good * x % (10 ** 9 + 7)
x = x * x % (10 ** 9 + 7)
i //= 2
return good
Analysis:
Time: O(logn), space: O(1).
Time: O(logn), space: O(1).