Count Good Numbers

Leetcode Problem:

• Count Good Numbers

Summary

• The problem is to find the total number of good digit strings of length n, where a good digit string is defined as a string where the digits at even indices are even and the digits at odd indices are prime (2, 3, 5, or 7).

Approach

• The solution uses dynamic programming and modular arithmetic to calculate the total number of good digit strings
• It first calculates the number of good digit strings for even and odd indices separately and then combines them to get the final result.

Complexity

• The time complexity of the solution is O(log n) due to the use of modular exponentiation, where n is the length of the input string.

Explanation

• The solution first defines a helper function powpow to calculate the modular exponentiation of a number
• It then calculates the number of good digit strings for even and odd indices separately using this function
• The number of good digit strings for even indices is calculated as 5^a, where a is the number of even indices, and the number of good digit strings for odd indices is calculated as 4^b, where b is the number of odd indices
• The final result is obtained by multiplying these two numbers together and taking the result modulo 10^9 + 7.

Solution Code:

struct powRet{
    long long ret;
    long long n;
};
class Solution {
public:
    const int MOD = 1000000007;
    powRet powpow(long long n, long long num){
        powRet ret;
        long long pow = num;
        long long nn = 1;
        long long beforePow = pow;
        long long beforenn = nn;
        while(nn <= n){
            nn *= 2;
            pow *= pow;
            pow %= MOD;
            if(nn > n) break;
            beforePow = pow;
            beforenn = nn;
        }
        ret.ret = beforePow;
        ret.n = beforenn;
        return ret;
    }
    int countGoodNumbers(long long n) {
        long long ans= 1;
        long long a = (n + 1)/2;
        long long b = n - a;
        while(a){
            powRet ret = powpow(a, 5);
            ans *= ret.ret;
            ans %= MOD;
            a -= ret.n;
        }
        while(b){
            powRet ret = powpow(b, 4);
            ans *= ret.ret;
            ans %= MOD;
            b -= ret.n;
        }
        return ans;
    }
};