RECURSION & BACKTRACKING › RECURSION PROBLEMS

Count Good Numbers

EasyEditorial · 6 minGenerated by gpt-5.6-luna · Aug 27

Open — the attempt gate is not wired up yet

This editorial is meant to unlock after you have run the problem at least once, with the worked solution behind one further deliberate click. That needs per-learner unlock state nothing stores today, so for now the whole article is open.

Try it yourself first →

Intuitionwhy each position can be counted independently

Every even index has exactly 5 legal digits, while every odd index has exactly 4 legal digits. The choice made at one position does not restrict any other position, so you multiply the number of choices across all positions instead of constructing the strings one by one. Leading zeros being allowed means index 0 has the same five choices as every other even index.

Among the indices from 0 through n - 1, the even indices are 0, 2, 4, and so on, giving (n + 1) / 2 positions using integer division. The remaining n / 2 positions are odd. Therefore the answer is 5 raised to the even-position count multiplied by 4 raised to the odd-position count. Since n can be as large as 10^15, compute both powers by squaring.

Approachcount position types, then exponentiate without expanding the power

Convert the input string to a 64-bit integer, because the value of n determines the position counts and the stated maximum fits in long long.
Compute even = (n + 1) / 2 and odd = n / 2, because indices start at zero and the even-indexed sequence has one extra position whenever n is odd.
Define modular exponentiation for a base and exponent, because multiplying the base once per position would require up to 10^15 iterations.
Start the power result at 1 and repeatedly inspect the current exponent bit; multiply the result by the current base only when that bit is set, because those selected powers of two form the requested exponent.
Square the base and divide the exponent by 2 after each iteration, because squaring changes the next power of two while halving removes the bit already processed.
Compute 5^even and 4^odd modulo MOD, multiply those two values modulo MOD, and return the result, because the independent choices combine by multiplication and every intermediate value must stay within the modulus.

Complexitythe exponent is reduced by half at every loop iteration

MEASURE	BOUND	WHY
Time	O(log n)	Each modular-power loop removes one binary digit of its exponent, so each of the two exponents is processed in logarithmically many iterations. Every iteration performs only a constant number of arithmetic operations.
Space	O(1) extra	The algorithm stores only a fixed number of counters, bases, results, and the input value; it does not allocate memory proportional to n. The returned integer is required output and is excluded from extra space.

Here n is the numeric value represented by the input string, and MOD is 10^9 + 7.

Annotated solutionC++ · iterative binary exponentiation · constant extra space

CPPCount the two kinds of positions and evaluate both powers with binary exponentiation.

#include <string>
using namespace std;

class Solution {
public:
    int countGoodNumbers(string n) {
        const long long MOD = 1000000007LL;
        long long length = stoll(n);
        long long even = (length + 1) / 2;
        long long odd = length / 2;

        long long evenWays = modPow(5, even, MOD);
        long long oddWays = modPow(4, odd, MOD);

        return static_cast<int>((evenWays * oddWays) % MOD);
    }

private:
    long long modPow(long long base, long long exponent, long long mod) {
        long long result = 1;
        base %= mod;

        while (exponent > 0) {
            if (exponent & 1) {
                result = (result * base) % mod;
            }
            base = (base * base) % mod;
            exponent >>= 1;
        }

        return result;
    }
};

The position formulas are the part most tightly connected to the zero-based indexing: (length + 1) / 2 counts indices 0, 2, 4, and so on, while length / 2 counts indices 1, 3, 5, and so on. In modPow, result is multiplied only for set exponent bits; squaring base then prepares the next power of two without ever building the full power.

Common mistakestwo wrong shapes that produce plausible answers

Previous · Pow(x, n)Every part of this item is done.