1922. Count Good Numbers
Problem Description
The problem requires us to calculate the total number of good
digit strings of a given length n
. A good
digit string is one where:
- The digits at even indices (0, 2, 4, ...) are even numbers (0, 2, 4, 6, 8).
- The digits at odd indices (1, 3, 5, ...) are prime numbers (2, 3, 5, 7).
The string is 0-indexed
, which means the indexing starts from 0. We are tasked with returning the count of such good strings modulo 10^9 + 7
to keep the number manageable since the count can be very large.
Intuition
The intuition behind the solution is to understand that since the digits at even and odd indices have separate and independent constraints, they can be handled separately. For digits at even positions, there are 5 choices (0, 2, 4, 6, 8), and for digits at odd positions, there are 4 choices (2, 3, 5, 7).
Given a string of length n
, half of the digits will be at even indices and half at odd indices (for odd values of n
, there will be one more digit at an even index since counting starts at 0). Hence, for strings of even length, we have a straightforward calculation:
- The number of ways to fill even indices = 5^(n/2).
- The number of ways to fill odd indices = 4^(n/2).
For odd lengths of n
, there is one extra even index, hence:
- The number of ways to fill even indices = 5^((n+1)/2).
- The number of ways to fill odd indices = 4^(n/2).
To find the total combinations, we multiply the number of ways to fill even indices with the number of ways to fill odd indices.
Since the calculations can result in very large numbers, we use modulo arithmetic to avoid overflow and keep the results within integer limits. The modulo used is 10^9 + 7
, which is a large prime number, that helps manage big numbers in competitive programming problems.
In our Python code, the myPow
function is a custom power function to calculate x^n under modulo. It uses the concept of binary exponentiation for efficient computation. It works by squaring the base x
and dividing the power n
by 2 at each iteration, and multiplying the result by x
when n
is odd. This process is repeated until n
reaches 0.
Finally, the return statement calculates the total number of good digit strings by multiplying 5^((n+1)/2)
by 4^(n/2)
using our custom power function and applies the modulo to get the answer.
Solution Approach
The solution to this problem mainly involves number theory and the efficient calculation of large powers under a modular system. Here's a breakdown of how it's implemented:
-
Binary Exponentiation Algorithm for Modular Exponentiation: The
myPow
function in the provided Python code is an implementation of the binary exponentiation algorithm, which calculatesx^n (mod m)
efficiently. The process involves iterating over the bits ofn
. For each bit that is set to 1 in the binary representation ofn
, we multiply the current result byx
to the corresponding power of 2 and take the result modulom
. After each iteration,x
is squared andn
is shifted right by one bit (essentially divided by 2). This is done untiln
is reduced to 0.Pseudocode for the
myPow
function is as follows:def myPow(x, n, mod): result = 1 while n > 0: if n % 2 == 1: result = (result * x) % mod x = (x * x) % mod n = n // 2 return result
-
Separation of Even and Odd Indices Constraints: The elegance of the solution lies in recognizing that the constraints for even and odd indices are separate and can thus be dealt with independently. Since at even indices only even digits can be placed, and at odd indices only prime digits can be placed, the problem reduces to two separate combinations problems.
-
Multiplication under Modulo: The solution multiplies the result of the powers for even and odd indices while always taking the modulo after each operation to prevent integer overflow. In Python, this is simply done with
% mod
after each multiplication. -
Handling Odd Lengths: The implementation accounts for odd lengths
n
by computing5^((n+1)/2)
for even indices instead of5^(n/2)
. This ensures that the extra even index in the case of an odd-length digit string is considered. -
Final Computation: The total number of good digit strings is derived by the formula:
total_good_strings = (myPow(5, (n + 1) // 2, mod) * myPow(4, n // 2, mod)) % mod
This formula ensures that all digits at even indices have been accounted for with
5
possible values each and all digits at odd indices are accounted for with4
possible values each.
The overall time complexity for this solution is O(log n)
due to the binary exponentiation, while the space complexity is O(1)
as it uses a constant amount of extra space.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a small example with n = 3
, which refers to a good digit string of length 3.
For n = 3
, an extra even index exists since we start from index 0. Therefore, we should have 1 odd index (index 1) and 2 even indices (indices 0 and 2).
The number of choices for the digit at even indices is 5 (0, 2, 4, 6, 8) and the number of choices for the digit at odd indices is 4 (2, 3, 5, 7).
Now, let's calculate the number of good digit strings:
- For even indices, there will be 2 digits, so the number of ways to fill them is 5 choices raised to the power of the number of even indices:
5^2 = 25
. - For the odd index, there will be a single digit, so the number of ways to fill it is 4 choices raised to the power of the number of odd indices:
4^1 = 4
.
To get the total number of good strings, we multiply the number of ways to place digits at even indices with the number of ways to place digits at odd indices:
Total good strings for n = 3
= 25 (even choices) * 4 (odd choice) = 100.
Now, since we must return this number modulo 10^9 + 7
, we do this simple calculation:
100 % (10^9 + 7) = 100.
So, the total number of good digit strings of length n = 3
is 100.
Using the myPow
function and the formula provided, we did the same computation programmatically:
- For the 2 even indices,
myPow(5, (3+1)//2, 10^9+7)
is called, which should return 25. - For the 1 odd index,
myPow(4, 3//2, 10^9+7)
is called, which should return 4.
Finally, we would have (25 * 4) % (10^9+7)
, which gives us the same result, 100, confirming that our solution approach is correct.
Solution Implementation
1class Solution:
2 def countGoodNumbers(self, n: int) -> int:
3 MODULO = 10**9 + 7
4
5 # Define the power function to calculate (x^n) % MODULO using binary exponentiation.
6 def my_pow(base, exponent):
7 result = 1
8 while exponent > 0:
9 # If exponent is odd, multiply the result with base.
10 if exponent % 2 == 1:
11 result = (result * base) % MODULO
12 # Square the base and reduce the exponent by half.
13 base = (base * base) % MODULO
14 exponent //= 2
15 return result
16
17 # Number of primes at odd positions is 5 (2,3,5,7). Hence, we use 5 as the base.
18 # Number of evens at even positions is 4 (0,2,4,6,8). Hence, we use 4 as the base. Even positions are considered 0-indexed here.
19 # The +1 is needed when n is odd, to calculate 5 raised to the (n//2 + 1).
20 return (my_pow(5, (n + 1) // 2) * my_pow(4, n // 2)) % MODULO
21
1class Solution {
2 // Define the modulus value as a constant for mod operations
3 private static final int MOD = 1000000007;
4
5 // This method calculates the count of good numbers
6 public int countGoodNumbers(long n) {
7 // Good numbers are created by even indices with 5 choices (0 to 4)
8 // and odd indices with 4 choices (0, 2, 4, 6, 8).
9 // We use exponentiation by squaring to compute the large powers efficiently
10 // We need to use (n+1)/2 for the power of 5 if n is odd.
11 // Similarly, we use n/2 for the power of 4, no matter if n is even or odd.
12 return (int) (myPow(5, (n + 1) / 2) * myPow(4, n / 2) % MOD);
13 }
14
15 // Helper method for fast exponentiation
16 private long myPow(long base, long exponent) {
17 long result = 1; // Start from the identity value
18 while (exponent != 0) {
19 if ((exponent & 1) == 1) {
20 // If the current exponent bit is 1, multiply the result by base
21 result = (result * base) % MOD;
22 }
23 // Square base and move to the next bit of the exponent
24 base = (base * base) % MOD;
25 exponent >>= 1; // Right shift exponent by 1 (equivalent to dividing by 2)
26 }
27 return result;
28 }
29}
30
1int kMod = 1000000007; // Define the modulo constant for large number arithmetic
2
3class Solution {
4public:
5 // Function to count the number of 'good' numbers of length n
6 int countGoodNumbers(long long n) {
7 // Calculate the product of 5^(n/2 + 1) and 4^(n/2) modulo kMod
8 // (n + 1) / 2 accounts for the case when n is odd and each part is good
9 // n / 2 ensures we deal with even number of digits for 4s
10 return static_cast<int>((myPow(5, (n + 1) / 2) * myPow(4, n / 2)) % kMod);
11 }
12
13private:
14 // Helper function to compute x^n % kMod efficiently
15 long long myPow(long long x, long long n) {
16 long long res = 1; // Initialize result to 1
17 while (n > 0) { // Loop until n becomes 0
18 if (n & 1) { // If n is odd, multiply res with x
19 res = res * x % kMod;
20 }
21 x = x * x % kMod; // Change x to x^2 for next iteration
22 n >>= 1; // Divide n by 2
23 }
24 return res; // Return the result of x^n
25 }
26};
27
1const kMod: number = 1000000007; // Define the modulo constant for large number arithmetic
2
3// Function to count the number of 'good' numbers of length n
4function countGoodNumbers(n: bigint): number {
5 // Calculate the product of 5^(ceil(n/2)) and 4^(floor(n/2)) modulo kMod
6 // Ceil is obtained by (n + 1n) / 2n which considers the case when n is odd
7 // Floor is n / 2n which ensures we deal with an even number of digits for 4s
8 return Number((myPow(BigInt(5), (n + 1n) / 2n) * myPow(BigInt(4), n / 2n)) % BigInt(kMod));
9}
10
11// Helper function to compute x^n % kMod efficiently
12function myPow(x: bigint, n: bigint): bigint {
13 let res: bigint = BigInt(1); // Initialize the result to 1
14 while (n > 0n) { // Loop until n becomes 0
15 if (n & 1n) { // If n is odd, multiply the result with x
16 res = (res * x) % BigInt(kMod);
17 }
18 x = (x * x) % BigInt(kMod); // Change x to x^2 for the next iteration
19 n >>= 1n; // Divide n by 2 by bitwise shift
20 }
21 return res; // Return the result of x^n
22}
23
Time and Space Complexity
The time complexity of the provided code is O(log n)
. This is because the key operation in the function is myPow
, which uses a binary exponentiation algorithm that computes x^n
by continually squaring x
and reducing n
by half at each step. As such, the number of steps required is proportional to the number of bits in n
, which is O(log n)
.
The space complexity of the code is O(1)
, meaning it is constant. The myPow
function uses only a fixed number of integer variables (res
and x
) that do not depend on the input size, and the computation is done in place without the need for additional space that scales with n
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which two pointer techniques do you use to check if a string is a palindrome?
Recommended Readings
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Donāt Miss This!