Introduction

Digit DP is a efficient technique for solving dynamic programming problems which involves building sequences. In this post Digit DP is used to build a digit sequence where no two adjacent digits are the same.

Problem

Our goal is to count the number of numbers between range $\left[a,b\right]$, where $0\leq a\leq b\leq10^{18}$ and no two adjacent digits are the same.

Approach

When using Digit DP for solving a problem we try to form a sequence until it satisfies given conditions. In our approach we start from the least significant digit (the rightmost digit) and move towards the most significant digit one digit a time.

Our function takes a number and returns the count of numbers between $0$ and the given number that satisfy our condition. This makes it easy to solve the problem for a given range $[a, b]$ by simply computing $f(b)-f(a-1)$.

We begin building our numbers from the least significant digit (the rightmost digit) and check whether the given conditions apply. The digit can not be equal to the neighboring digit. We also have to check that the number we are building does not get bigger than the number given as a parameter.

Let $i$ be the current position, $\mathrm{num}$ the the number we are building and $s$ a string representation of the number passed to our function. $\mathrm{num}_i$ has to satisfy two conditions:

\[\mathrm{num}_{i}\neq\mathrm{num}_{i-1} \\\\ \mathrm{num}_i\le s_i\]

Implementation

We implement a function $f$ that takes a string representation $s$ of a number. Our DP state is

\[dp[n][cond][digits].\]

$digits$ contains digits between $0$ and $9$. $n$ keeps track of the digits starting from the most significant number to the least significant number. When building our sequence we need to make sure that the number represented by the sequence is smaller than the number $s$. For this $cond$ is used.

The initial states are formed for two conditions ($cond=0$ and $cond=1$):

  1. $dp[n-1][1][d]=\begin{cases}1 &,~d\leq s[n-1] \\ 0 &,~d>s[n-1]\end{cases}$
  2. $dp[n-1][0][d]=1$

The states for $0\leq i\leq n-2$ are formed following a similar idea:

  1. $dp[i][1][d]=\begin{cases}\sum_{k\neq d}dp[i+1][0][k] &,~d<s[i] \\ \sum_{k\neq d}dp[i+1][1][k] &,d~=s[i] \\ 0 &,~d>s[i]\end{cases}$
  2. $dp[i][0][d]=\sum_{k\neq d}dp[i+1][0][k]$

We can obtain the count of valid numbers with

\[c=\sum_{d}dp[0][1][d].\]

We can check our current logic with an exampe. Let $s=23$.

Initial states for $cond=1$:

\[0,~1,~2,~3\]

Initial sates for $cond=0$:

\[0,~1,~2,~3,~4,~5,~6,~7,~8,~9\]

Next states for $cond=1$:

\[01,~02,..,~09,~10,~12,~13,..,~19,~20,~21,~23\]

Next states for $cond=0$:

\[01,~02,..,~09,~10,~12,~13,..,~19,~20,~21,~23,..,~29\]

We can notice that one valid sequence is missing: $00$. This is due to our logic not taking into account the numbers that have adjacent “padding” zeros on the left side of valid digits such as $00,~0012,~\mathrm{and}~003104$.

This can be fixed by adding a term to our count such that

\[c=\sum_{d}dp[0][1][d]+\sum_{i=1}^{n-1}dp[i][0][0].\]

And that is it! We obtain the count of numbers in the range $\left[a, b\right]$ where no two adjacent digits are the same by computing

\[g(a,b)=\begin{cases}f(b)-f(a-1) &,~a>0 \\\\ f(b) &,~a=0\end{cases}~.\]

If you have any comments or corrections to the logic feel free to email me!