# Digit DP

Author: Jesse Choe

Contributors: Nathan Wang, Chuyang Wang, Daniel Ge

Finding the number of integers in a range that have a property.

### Prerequisites

Focus Problem – try your best to solve this problem before continuing!

## General Resources

Resources | ||||
---|---|---|---|---|

AR | ||||

GFG | ||||

YouTube | Great introduction video | |||

CF |

Digit DP is a technique used to solve problems that asks you to find the number of integers within a range that satisfies some property based on the digits of the integers. Typically, the ranges are between large integers (such as between $1$ to $10^{18}$), so looping through each integer and checking if it satisfies the given property is too slow. Digit DP uses the digits of the integers to quickly count the number of integers with the given property in the range of integers.

## Solution - Odometer

### Without Dynamic Programming

We can solve this problem in $\mathcal{O}(Y - X)$ time by looping through $X \ldots Y$ and checking whether a given number is an interesting number. However, since $Y - X$ can be large, the naive solution is too slow, requiring us to optimize it.

### With Dynamic Programming

One way to optimize the brute force approach of looping from $X$ to $Y$ and counting interesting numbers is by using dynamic programming. The DP approach involves considering all 9 digits one at a time to occupy at least half of the number.

Let $\texttt{dp[pos][k][under][started]}$ where $\texttt{pos}$ is the current position, $\texttt{k}$ is a counter to see if you have at least half of the same digit, $\texttt{under}$ is whether you have gone below the actual number, and $\texttt{started}$ is a boolean if you still have leading zeros. The transition involves looping through 9 digits to add to the current location and comparing with the digit we want to occupy at least half of the number.

Given the current state $\texttt{dp[pos][k][under][started]}$, we loop through all digits from 0 to 9 and consider adding each of them to the current position. If we add the digit $d$ to the current position, we update our state as follows:

- If $d$ is less than the $i$-th digit of the actual number $Y$, then we set $\texttt{under}$ to true.
- If $d$ is not zero or $\texttt{started}$ is already true, then we set $\texttt{started}$ to true.
- If $d$ is equal to the digit we are interested in, then we increment $k$.
- If $k$ is greater than $\lfloor \frac{i+1}{2} \rfloor$, then we increment our count of interesting numbers by 1.
- We move on to the next position by setting $i$ to $i+1$ and transitioning to the next state.

This algorithm is fast enough as the number of digits is small and there are only nine digits.

C++

#include <bits/stdc++.h>using namespace std;using ll = long long;ll dp[19][50][2][2]; // dp[pos][k][under][started]string num;/** Reset the dp array to its initial values. */void reset() {

Java

import java.io.*;import java.util.*;public class Odometer {// dp[pos][count][under][started]static long[][][][] dp = new long[19][50][2][2];static String num;/** Reset the dp array to its initial values. */public static void reset() {

## Problems

Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|

CF | Easy | ## Show TagsBinary Search, DP | |||

CF | Easy | ## Show TagsDP | |||

SPOJ | Easy | ## Show TagsDP | |||

CF | Normal | ## Show TagsDP | |||

CC | Normal | ## Show TagsDP |

## USACO

Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|

Gold | Normal | ## Show TagsDP | |||

Gold | Hard | ## Show TagsDP |

### Module Progress:

### Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!