In this guide, you will get 1922. Count Good Numbers LeetCode Solution with the best time and space complexity. The solution to Count Good Numbers problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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).
For example, “2582” is good because the digits (2 and 8) at even positions are even and the digits (5 and 2) at odd positions are prime. However, “3245” is not good because 3 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
Complexity Analysis
Time Complexity: O(\log n)
Space Complexity: O(\log n)
1922. Count Good Numbers LeetCode Solution in C++
class Solution {
public:
int countGoodNumbers(long long n) {
return modPow(4 * 5, n / 2) * (n % 2 == 0 ? 1 : 5) % kMod;
}
private:
static constexpr int kMod = 1'000'000'007;
long modPow(long x, long n) {
if (n == 0)
return 1;
if (n % 2 == 1)
return x * modPow(x, n - 1) % kMod;
return modPow(x * x % kMod, n / 2);
}
}; /* code provided by PROGIEZ */
1922. Count Good Numbers LeetCode Solution in Java
class Solution {
public int countGoodNumbers(long n) {
return (int) (modPow(4 * 5, n / 2) * (n % 2 == 0 ? 1 : 5) % kMod);
}
private static final int kMod = 1_000_000_007;
private long modPow(long x, long n) {
if (n == 0)
return 1;
if (n % 2 == 1)
return x * modPow(x, n - 1) % kMod;
return modPow(x * x % kMod, n / 2);
}
} // code provided by PROGIEZ
1922. Count Good Numbers LeetCode Solution in Python
class Solution:
def countGoodNumbers(self, n: int) -> int:
kMod = 1_000_000_007
def modPow(x: int, n: int) -> int:
if n == 0:
return 1
if n % 2 == 1:
return x * modPow(x, n - 1) % kMod
return modPow(x * x % kMod, n // 2)
return modPow(4 * 5, n // 2) * (1 if n % 2 == 0 else 5) % kMod # code by PROGIEZ
