Sitemap
Open in app

Sign in

Medium Logo
Write

Sign in

Digit DP coding pattern

Dilip Kumar
13 min readApr 22, 2025

Digit DP is a powerful technique used to count numbers within a given range [L, R] that satisfy a specific property related to their digits.

Chapter#1: Core concept

1.1 Core Idea

Instead of iterating through every number from L to R (which is often too slow, especially for large ranges like up to 10¹⁸), Digit DP builds the numbers digit by digit from left to right and uses recursion with memoization to count how many valid numbers can be formed.

We can simply apply level, check, choice, and move concept we have studied in the Dynamic Programming course.

Let’s say we want to count numbers from 0 to n=324 . Instead of running for loop to iterate 0...n , we can generate these numbers by placing possible choices on the given level.

At every position i we need to find out the possible choices. Since we have given upper limit as S=324 therefore the first position i=0 can only be filled with 0 or 1 or 2 or 3 .

After we fill first position, for the second position we have two categories .

  1. i=0 was filled with < 3 i..e. 0 or 1 or 2: In this case for i=1, we have 0…9 choices.
  2. i=0 was filled with 3: In this case we have just 0, 1 and 2 choices.

To handle the boundary condition for move, we need to introduce tight variable in the recursion method as below.

f(i,tight) = Count numbers generated with positions 0---i with given tight bool flag
f(i,tight) = 0....9 choices if tight == false
              -> This will move to tight = false
           = 0....s[i] choices if tight == true
              -> This will move to tight = true

Following is recursion tree for reference.

Following is code for reference.

#include <iostream>
using namespace std;

int solve(string s, int i, bool tight) {
    int len = s.size();
    // Base case: end of string
    if (i == len) {
        return 1; // To count the numbers
    }
    int count = 0;
    int digit = (s[i] - '0'); // convert char to int
    int upper_bound = tight ? digit : 9; // Possible choices
    for(int d=0; d <= upper_bound; d++) {
        bool new_tight = (tight && d == digit); // Move state
        count += solve(s, i+1, new_tight);
    }
    return count;
}

int main() {
    int n = 324;
    int count = solve(to_string(n), 0, true);
    cout <<count<<endl;
    return 0;
}

Time complexity

we have number n and len=size(n) . There are two ways to write the time complexity.

  1. In terms of (i&tight) : Here i goes from 0….len and tight is either 0 or 1. Since we have not applied memoization therefore time complexity will be O(10^len)
  2. In terms of n: Since we generate each number from 0…n, therefore time compleixty would be O(n)

Technically both are same. Let’s say n=999 , then len=3 it will lead to 10^3~1000 time complexity which is same as O(n).

1.2 Constraints and memoization

Once we understand the core of digit dp, rest of applying constraints based on different problem is simply extension of recursion and dynamic programming concept.

Moment we apply constraints, it leads to repetition of recursion function call therefore we can apply memoization to optimize it.

Let’s solve following problem to understand it.

Problem: Counting numbers up to N where the sum of digits is less than or equal to a given value K.

Given two non-negative integers N and K, find the count of integers x such that 0 <= x <= N and the sum of the digits of x is less than or equal to K.

Example:

N = 100, K = 3
Numbers to count: 0, 1, 2, 3, 10, 11, 12, 20, 21, 30, 100.
Sums of digits: 0, 1, 2, 3, 1, 2, 3, 2, 3, 3, 1.
All these sums are <= 3.
Ans: The count is 11.

Approach#1: Bruteforce to iterate each number and check for constraints

Following is code using bruteforce approach.

#include <iostream>
using namespace std;
int solve(int n, int k) {
    int ans =0;
    for (int i=0; i <=n; i++) {
        // sum the digits
        int sum = 0;
        int num = i;
        while(num != 0) { // Iterate each digit of num
           sum += (num%10);
           num = num/10;
        }
        if(sum <=k) {
          ans++;  
        }
    }
    return ans;
}
int main() {
    int n = 100;
    int k = 2;
    int count = solve(n, k);
    cout <<count<<endl;
    return 0;
}

Time complexity: O(n*d) where d is avg digits in number.

Can we improve the time complexity?

Approach #2: Use Digit dp

  • Since we need to keep track of digit sum therefore we need introduce current_sum to track it and apply the check.
  • We can apply memoization as there is repetition in recursive call.

Following is recursive code with memoization

// Online C++ compiler to run C++ program online
#include <iostream>
#include <vector>
using namespace std;

int solve(string s, int k, int i, bool tight, int current_sum, vector<vector<vector<int>>> & dp) {
    int len = s.size();
    // Base case: end of string
    if (i == len) {
        return 1; // To count the numbers
    }

    // Memoization check
    if(dp[i][tight][current_sum] != -1) {
       return  dp[i][tight][current_sum];
    }
    int count = 0;
    // Determine the possible choices
    int digit = (s[i] - '0'); // convert char to int
    int upper_bound = tight ? digit : 9;
    for(int d=0; d <= upper_bound; d++) {
        bool new_tight = (tight && d == digit);
        int new_sum = current_sum + d;
        // Apply check
        if(new_sum <= k) {
            count += solve(s, k, i+1, new_tight, new_sum, dp);
        }
    }
    dp[i][tight][current_sum] = count;
    return count;
}

int main() {
    int n = 234235;
    int k = 3;
    string s = to_string(n);
    int len = s.size();
    int size = 9*len;
    vector<vector<vector<int>>> dp(len, vector<vector<int>>(2, vector<int>(size,-1)));
    int count = solve(s, k, 0, true, 0, dp);
    cout <<count<<endl;
    return 0;
}

1.3 Leading zero check

Since leading zeros don’t affect the numerical value (e.g., 007 is the same as 7) therefore many times we don’t need this check. Following are few to explain the leading zero concept.

Digit DP Builds Padded Numbers: When we use Digit DP to count numbers up to N, we conceptually process all numbers as if they have the same number of digits as N, padding shorter numbers with leading zeros.

  • For N = 100, we process 3 digits.
  • The number 7 is processed conceptually as 007.
  • The number 21 is processed conceptually as 021.
  • The number 0 is processed conceptually as 000.

Sum Calculation Must Match the Actual Number: The goal is to calculate the sum of digits of the actual number represented, not the padded representation.

  • For 007, the actual number is 7, and the sum is 7.
  • For 021, the actual number is 21, and the sum is 2 + 1 = 3.
  • For 000, the actual number is 0, and the sum is 0.

Where’s the issue? You don’t see leading zero issue in these cases. Still, let’s understand how to code it as we will see it’s usage while solving the problems.

Following is code block to add zero check.

bool new_leading_zero = leading_zero && d == 0;

Following is updated code including leading zero check for previous problem as reference.

// Online C++ compiler to run C++ program online
#include <iostream>
#include <vector>
using namespace std;

int solve(string s, int k, int i, bool tight, bool leading_zero, int current_sum,  vector<vector<vector<vector<int>>>> & dp) {
    int len = s.size();
    // Base case: end of string
    if (i == len) {
        return 1; // To count the numbers
    }

    // Memoization check
    if(dp[i][tight][leading_zero][current_sum] != -1) {
      return  dp[i][tight][leading_zero][current_sum];
    }
    int count = 0;
    // Determine the possible choices
    int digit = (s[i] - '0'); // convert char to int
    int upper_bound = tight ? digit : 9;
    for(int d=0; d <= upper_bound; d++) {
        bool new_tight = (tight && d == digit);
        int sum_contribution = 0;
        if(!leading_zero) { // Only add if it's not a leading zero
           sum_contribution = d; 
        } else if (leading_zero && d > 0) { // First non-zero digit
            sum_contribution = d; 
        }
        int new_sum = current_sum + sum_contribution;
        bool new_leading_zero = leading_zero && d == 0;
        // Apply check
        if(new_sum <= k) {
            count += solve(s, k, i+1, new_tight, new_sum,new_leading_zero, dp);
        }
    }
    dp[i][tight][leading_zero][current_sum] = count;
    return count;
}

int main() {
    int n = 234235;
    int k = 3;
    string s = to_string(n);
    int len = s.size();
    int size = 9*len;
    vector<vector<vector<vector<int>>>> dp(len, vector<vector<vector<int>>>(2, vector<vector<int>>(2, vector<int>(size,-1))));
    int count = solve(s, k, 0, true, true, 0, dp);
    cout <<count<<endl;
    return 0;
}

Chapter #2: Leetcode problems using DigitDP core concept

233. Number of Digit One

https://leetcode.com/problems/number-of-digit-one/description/

Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.

Example 1:

Input: n = 13
Output: 6 (0,1,2,3,4,5,6,7,8,9,10,11,12,13 => 1,10,11,12,13 => 6)

Approach # Use digit dp

We can simply apply digit dp with memoization to solve this problem. One additional state we need is to count ones seen so far. Following is code for reference.

class Solution {
private:
    int solve(string s, int i, bool tight, int one_count,
              vector<vector<vector<int>>>& dp) {
        int n = s.size();
        // Base case: end of number
        if (i == n) {
            return one_count;
        }
        if (dp[i][tight][one_count] != -1) {
            return dp[i][tight][one_count];
        }
        int count = 0;
        int digit = s[i] - '0';
        int upper_bound = tight ? digit : 9;
        for (int d = 0; d <= upper_bound; d++) {
            int next_tight = (tight && d == digit);
            int next_one_count = (d == 1 ? one_count + 1 : one_count);
            count += solve(s, i + 1, next_tight, next_one_count, dp);
        }
        dp[i][tight][one_count] = count;
        return count;
    }

public:
    int countDigitOne(int n) {
        string s = to_string(n);
        int size = s.size();
        int one_count = 10;
        vector<vector<vector<int>>> dp(
            size, vector<vector<int>>(2, vector<int>(one_count, -1)));
        return solve(s, 0, true, 0, dp);
    }
};

1012. Numbers With Repeated Digits

https://leetcode.com/problems/numbers-with-repeated-digits/description/

Given an integer n, return the number of positive integers in the range [1, n] that have at least one repeated digit.

Example 1:

Input: n = 100
Output: 10
Explanation: The positive numbers (<= 100) with atleast 1 repeated digit are 11, 22, 33, 44, 55, 66, 77, 88, 99, and 100.

Approach# Apply digit dp

  1. We can use digit dp to build numbers.
  2. To detect the duplicate digits, we can use mask

Following is code for reference.

class Solution {
private:
    int solve(string s, int i, bool tight, int mask, bool repeated,
              bool leading_zero, vector<vector<vector<vector<int>>>>& dp) {
        int size = s.size();
        if (i == size) {
            return repeated ? 1 : 0;
        }
        if (dp[i][tight][repeated][mask] != -1) {
            return dp[i][tight][repeated][mask];
        }
        int count = 0;
        int digit = s[i] - '0';
        int upper_bound = tight ? digit : 9;
        for (int d = 0; d <= upper_bound; d++) {
            bool new_repeated = repeated;
            int new_mask = mask;
            if (!leading_zero || d > 0) {
                new_repeated = repeated || (mask & 1 << d);
                new_mask = (mask | 1 << d);
            }
            bool new_leading_zero = (leading_zero && d == 0);
            int new_tight = (tight && d == digit);
            count += solve(s, i + 1, new_tight, new_mask, new_repeated,
                           new_leading_zero, dp);
        }
        dp[i][tight][repeated][mask] = count;
        return count;
    }

public:
    int numDupDigitsAtMostN(int n) {
        string s = to_string(n);
        int len = s.size();
        int mask_size = pow(2, 10);
        vector<vector<vector<vector<int>>>> dp(
            len, vector<vector<vector<int>>>(
                     2, vector<vector<int>>(2, vector<int>(mask_size, -1))));
        return solve(s, 0, true, 0, false, true, dp);
    }
};

2376. Count Special Integers

https://leetcode.com/problems/count-special-integers/description/

We call a positive integer special if all of its digits are distinct.

Given a positive integer n, return the number of special integers that belong to the interval [1, n].

Example 1:

Input: n = 20
Output: 19
Explanation: All the integers from 1 to 20, except 11, are special. Thus, there are 19 special integers.

Approach # 1 : Using repeated digit count

We can leverage the previous problem and solve unique as below.

unique = N — repeated

Following is code for reference.

public:
    int countSpecialNumbers(int n) {
        int repeated = numDupDigitsAtMostN(n);
        return n - repeated;
    }
};

Approach # 2: Using digit count to count unique digits

This can be more simplified as below.

  1. mask is act as a set.
  2. if mask & 1 <<d then skip the digit
  3. We don’t need unique parameter (similar to repeated in previous code)

Following is code for reference.

class Solution {
private:
    int solve(string s, int i, bool tight, int mask, bool leading_zero,
              vector<vector<vector<int>>>& dp) {
        int size = s.size();
        if (i == size) {
            return leading_zero ? 0 : 1;
        }
        if (dp[i][tight][mask] != -1) {
            return dp[i][tight][mask];
        }
        int count = 0;
        int digit = s[i] - '0';
        int upper_bound = tight ? digit : 9;
        for (int d = 0; d <= upper_bound; d++) {
            int new_mask = mask;
            if (!leading_zero || d > 0) {
                if (mask & 1 << d) {
                    continue; // skip if mask already has bit set
                }
                new_mask = mask | 1 << d;
            }
            bool new_leading_zero = (leading_zero && d == 0);
            int new_tight = (tight && d == digit);
            count += solve(s, i + 1, new_tight, new_mask, new_leading_zero, dp);
        }
        dp[i][tight][mask] = count;
        return count;
    }

public:
    int countSpecialNumbers(int n) {
        string s = to_string(n);
        int len = s.size();
        int mask_size = pow(2, 10);
        vector<vector<vector<int>>> dp(
            len, vector<vector<int>>(2, vector<int>(mask_size, -1)));
        return solve(s, 0, true, 0, true, dp);
    }
};

902. Numbers At Most N Given Digit Set

https://leetcode.com/problems/numbers-at-most-n-given-digit-set/description/

Given an array of digits which is sorted in non-decreasing order. You can write numbers using each digits[i] as many times as we want. For example, if digits = ['1','3','5'], we may write numbers such as '13', '551', and '1351315'.

Return the number of positive integers that can be generated that are less than or equal to a given integer n.

Example 1:

Input: digits = ["1","3","5","7"], n = 100
Output: 20
Explanation: 
The 20 numbers that can be written are:
1, 3, 5, 7, 11, 13, 15, 17, 31, 33, 35, 37, 51, 53, 55, 57, 71, 73, 75, 77.

Approach# Apply digit dp

  • If number is leading with zero then we can use 0 as an extra digit.
  • Use binary search to find out the index as below
  1. if match is found then return the same index as boundary
  2. If no match then we have following three conditions

a. It is somewhere in the between: In this case return distance — 1

b. It is higher than all the num therefore equal to end: In this case return size -1

c. If it is lower than all the numbers then return -1

Note: Since count does include 0 as a value therefore deduct 1 from the final answer.

Following is code for reference.

class Solution {
private:
    int search(vector<int>& digits, int target) {
        auto itr = lower_bound(digits.begin(), digits.end(), target);

        // If match then return the index
        if (itr != digits.end()) {
            if (*itr == target) {
                return distance(digits.begin(), itr);
            }
            return distance(digits.begin(), itr) - 1;
        }
        // If match to the end
        if (itr == digits.end()) {
            return digits.size() - 1;
        }
        // for begin, return -1
        return -1;
    }
    int solve(string s, vector<int>& digits, int i, bool tight,
              bool leading_zero, vector<vector<vector<int>>>& dp) {
        int len = s.size();
        if (i == len) {
            return 1;
        }
        if (dp[i][tight][leading_zero] != -1) {
            return dp[i][tight][leading_zero];
        }
        int count = 0;
        int digit = s[i] - '0';
        // special case for zero
        if (leading_zero) {
            count += solve(s, digits, i + 1, false, leading_zero, dp);
        }
        int upper_bound = tight ? search(digits, digit) : digits.size() - 1;
        for (int j = 0; j <= upper_bound; j++) {
            int d = digits[j];
            bool new_tight = tight && d == digit;
            bool new_leading_zero = leading_zero && (d == 0);
            count += solve(s, digits, i + 1, new_tight, new_leading_zero, dp);
        }
        dp[i][tight][leading_zero] = count;
        return count;
    }

public:
    int atMostNGivenDigitSet(vector<string>& digits, int n) {
        vector<int> nums;
        for (string digit : digits) {
            nums.push_back(stoi(digit));
        }
        string s = to_string(n);
        int len = s.size();
        vector<vector<vector<int>>> dp(
            len, vector<vector<int>>(2, vector<int>(2, -1)));
        return solve(s, nums, 0, true, true, dp) - 1;
    }
};

600. Non-negative Integers without Consecutive Ones

https://leetcode.com/problems/non-negative-integers-without-consecutive-ones/description/

Given a positive integer n, return the number of the integers in the range [0, n] whose binary representations do not contain consecutive ones.

Example 1:

Input: n = 5
Output: 5
Explanation:
Here are the non-negative integers <= 5 with their corresponding binary representations:
0 : 0
1 : 1
2 : 10
3 : 11
4 : 100
5 : 101
Among them, only integer 3 disobeys the rule (two consecutive ones) and the other 5 satisfy the rule.

Approach: Use DigitDp

  1. We can first convert given n into binary representation, this will give us upper bound.
  2. Then instead of building the decimal number, we will build binary number with only allowed digits are 0 and 1
  3. Will also track the previously used digit to skip 1 as option to avoid consecutive 1
class Solution {
private:
    vector<int> toBinary(int n) {
        vector<int> binary;
        while (n != 0) {
            binary.push_back(n % 2);
            n = n / 2;
        }
        reverse(binary.begin(), binary.end());
        return binary;
    }
    int solve(vector<int>& num, int i, bool tight, int prev_digit,
              vector<vector<vector<int>>>& dp) {
        int len = num.size();
        if (i == len) {
            return 1;
        }
        if (dp[i][tight][prev_digit] != -1) {
            return dp[i][tight][prev_digit];
        }
        int count = 0;
        int upper_bound = tight ? num[i] : 1;
        for (int d = 0; d <= upper_bound; d++) {
            bool new_tight = tight && d == num[i];
            // Skip if current and prev digit both are 1
            if (d == 1 && prev_digit == 1) {
                continue;
            }
            count += solve(num, i + 1, new_tight, d, dp);
        }
        dp[i][tight][prev_digit] = count;
        return count;
    }

public:
    int findIntegers(int n) {
        vector<int> num = toBinary(n);
        int len = num.size();
        vector<vector<vector<int>>> dp(
            len, vector<vector<int>>(2, vector<int>(2, -1)));
        return solve(num, 0, true, 0, dp);
    }
};

Practice problems

https://leetcode.com/problems/find-all-good-strings/

https://leetcode.com/problems/rotated-digits/description/

https://leetcode.com/problems/stepping-numbers/

https://www.spoj.com/problems/PR003004/

Chapter#3: Dual bound

Count number between range L and R.

Chapter#4: Triple bound

Count non decreasing digit ≤N

This post is based on interaction with https://aistudio.corp.google.com/.

Happy learning :-)

Digit Dp
Coding Interviews

--

--

Dilip Kumar
Dilip Kumar

Written by Dilip Kumar

554 followers
29 following

With 18+ years of experience as a software engineer. Enjoy teaching, writing, leading team. Last 4+ years, working at Google as a backend Software Engineer.

Responses (1)

Help

Status

About

Careers

Press

Blog

Privacy

Rules

Terms

Text to speech