Digit Dynamic Programming

Digit DP counts integers through their decimal representations instead of iterating up to a huge numeric bound. We count values in [0, N] with no equal adjacent digits in their ordinary representation. The state remembers the previous real digit, whether the number has started, and whether its prefix still equals the bound. Leading padding zeros are not ordinary digits of shorter numbers.

Prerequisites: Memoization; decimal digits; state sufficiency.

Build the idea

1. Recognize the repeated subproblems

   N can be as large as 10^18, so enumerating values is impossible, while its decimal representation has at most 19 positions. Many different smaller prefixes share the same remaining length, previous digit and constraint status. A DP on those features has only a few thousand transitions rather than a loop proportional to N.

2. Define the state

   count(pos, last, tight, started) counts valid suffix choices from the current digit position. tight means the fixed prefix exactly matches N’s prefix, so the next digit is bounded. started indicates whether a nonpadding digit has appeared. last is 0…9 after starting, or sentinel 10 before it. These variables retain all information relevant to adjacent equality and the upper bound.

3. Derive the transition

   Try digits 0…limit, where limit is N[pos] if tight and 9 otherwise. New tight remains true only if it was true and the chosen digit equals the bound digit. Before starting, a zero stays padding and does not update last. Otherwise reject a digit equal to last when already started, then recurse with that real digit. Each digit string is considered once.

   $$\mathrm{newTight}=\mathrm{tight}\mathrm{AND}(\mathrm{digit}=\mathrm{bound}[\mathrm{pos}\left]\right)$$

4. Base cases and computation order

   At the end return one for every accepted representation, including the never-started path, which denotes zero once. Initialize memo entries to −1 and cache every state, including tight states because N is fixed for this run. Position always increases, so recursive dependencies are acyclic and depth≤19. If counting a different zero property, the terminal case would need adjustment.

5. Correctness and invariant

   Every integer≤N has one length-N zero-padded representation. tight exactly characterizes which choices remain≤N, while started removes only padding from the adjacency rule. The transition accepts precisely ordinary representations without equal neighbors. Disjoint next-digit choices justify addition, and memoization merges states with identical future restrictions. This is counting, so a too-small state can silently double-count or admit invalid prefixes.

6. Work the example

   For N=20, the range contains 21 integers. Only 11 has equal adjacent real digits, so the answer is 20. Short numbers such as 1 are represented with padding 01 but are valid:the leading zero does not become a previous real digit. Zero follows the all-padding terminal convention and is included.

   bound range	excluded	valid count
   0..9	none	10
   0..10	none	11
   0..11	11	11
   0..20	11	20

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<string>
#include<cstring>
std::string bound;
long long memo[20][11][2][2];
long long count(int pos,int last,int tight,int started){
    if(pos==(int)bound.size()){
        return 1; // The never-started representation denotes zero, counted once.
    }
    long long&result=memo[pos][last][tight][started];
    if(result!=-1){
        return result;
    }
    result=0;
    int limit=tight?bound[pos]-'0':9;
    for(int digit=0;digit<=limit;++digit){
        int nextTight=tight&&(digit==limit);
        if(!started&&digit==0){
            result+=count(pos+1,10,nextTight,0);
        }
        else if(!started||digit!=last){
            result+=count(pos+1,digit,nextTight,1);
        }
    }
    return result;
}
int main(){
    std::cin>>bound;
    std::memset(memo,-1,sizeof memo);
    std::cout<<count(0,10,1,0)<<'\n';
}

Complexity analysis

At most L·11·2·2 states for L≤19, each trying≤10 digits:O(L·11·4·10) time, O(L·11·4) cache plus O(L) recursion. Counts≤N+1 fit long long under the bound; there is no modulo in this program.

Example input and output

Read an integer N in decimal,0≤N≤10^18. Print the exact count in [0, N] whose ordinary decimal representation has no adjacent equal digits. Zero is valid and counted once.

Input

20

Output

20

For N=20, the range contains 21 integers. Only 11 has equal adjacent real digits, so the answer is 20. Short numbers such as 1 are represented with padding 01 but are valid:the leading zero does not become a previous real digit. Zero follows the all-padding terminal convention and is included.

Practical applications

Use to count values with digit properties under large bounds; range [A, B] can use F(B)−F(A−1), handling A=0 separately. Digit sums, remainder classes and pattern avoidance add their own state dimensions and complexity factors.

Check your understanding

Why must leading padding zeros be treated separately?

Put it into practice

Brute-force all bounds up to a few thousand and compare.