Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is Digit DP?
3.
Problem Statement
3.1.
Constraints:
3.2.
Input
3.3.
Output
3.4.
Explanation:
4.
Approach
4.1.
Method 1: Recursion
5.
Algorithm
5.1.
Program
6.
C++
6.1.
Output
6.2.
Complexity Analysis
7.
Method 2: DP with Memoization
7.1.
Algorithm
7.2.
Program
8.
C++
8.1.
Output
8.2.
Complexity Analysis
9.
Frequently Asked Question 
9.1.
What is the digit DP?
9.2.
What is the complexity of digit DP?
9.3.
What is the time required for dynamic programming?
10.
Conclusion
Last Updated: Mar 27, 2024
Medium

Introduction to digit DP

Author Pranav Gautam
2 upvotes
gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up

Introduction

In the dynamic world of computer science, "Digit DP" stands as a compelling offshoot of dynamic programming, addressing numerical challenges involving digits and arithmetic. "Digit DP" refers to a technique in dynamic programming used to solve problems related to numerical computations and operations involving digits. 

digit dp

In this article, we will discuss about what Digit DP is. Then we will discuss approaches to solve this problem. 

What is Digit DP?

Digit DP is a type of DP problem. Problems falling into digit DP follow a typical problem structure. Usually, in a Digit DP problem, a number range (say from ‘A’ to ‘B’) is given as input. The solution has to be built for the numbers falling into the given number range. For a better understanding, let’s consider a typical digit problem. With this sample problem, we will discuss the common steps that must be followed to solve a digit DP problem.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Problem Statement

Given two numbers as ‘LOW’ and ‘HIGH’ extremes for a range of numbers, find the value of the function sum(‘LOW’,  ‘HIGH’ ). The function sum(‘LOW’, ‘HIGH’ ) returns the sum of all the digits lying between ‘LOW’ and ‘HIGH’ inclusively.

Constraints:

1 ≤ ‘LOW’ < ‘HIGH’ ≤ 1018

Input

Enter low: 9
Enter high: 13

Output

Digit Sum:  19

Explanation:

Numbers Between 9 and 13 Digits                               Sum of Digits
9 9 9
10 1,0 1
11 1,1 2
12 1,2 3
13 1,3 4
                                                                   Sum(9,13) 19

Approach

The function Sum(‘LOW’, ‘HIGH’) can be rewritten as:

Sum(LOW, HIGH) = (LOW) + (LOW + 1) + (LOW + 2) + . . .  + (HIGH - 1) + (HIGH). -eq(1)

Similarly, Sum(1, LOW- 1) and Sum(1, HIGH) can be written as:

Sum(1, LOW- 1) = 1 + 2 + 3 + 4 . . . + (LOW - 2)+ (LOW - 1) -eq(2)

Sum(1, HIGH) = 1 + 2 + 3 + 4 . . . + (HIGH - 1)+ (HIGH) -eq(3)

Using eq(3) and eq(2) in eq(1), Sum(LOW, HIGH) can be rewritten as:

Sum(LOWHIGH) = Sum(1, HIGH) - Sum(1, LOW- 1)

For a better understanding, refer to the figure given below:

So, we need to create a function SUM_OF_DIGITS(N) which can find the sum of digits of numbers lying in the range of 1 to ‘N’. Thus, a function f(a,b) is transformed as:

f(a,b) = g(b) - g(a-1) where g = f(a,1).

Method 1: Recursion

Let’s say we need to find the value of SUM(100, 625). As discussed in the Approach section, SUM(100,625) can be calculated as SUM(1,625) - SUM(1,99). 

Consider calculating the value of SUM(1,625) first. The value of SUM(1,99) can be calculated similarly. The number of digits in 625 is 3. So, the maximum number of digits possible for a number in the given range is 3. Assume a 3-digit number with no values set yet. It may look like the figure given below:

The most significant digit in 625 is 6. So, the most significant digit of Number ‘X’ can only have a value from 1 to 6. If the value of the most significant digit in Number X is less than 6, then the other digits of Number X can have any value as all the numbers so formed will have a value less than 625. Refer to the figure given below for illustration.

What if the value of Most Significant Digit in Number ‘X’ is 6? In that case, the value of the 2nd most significant digit of Number ‘X’ should be less than that of the given number. Consider the figure given below for a better understanding of this case.

So, for a given position in the Number ‘X’ we need to check if the previous position in Number ‘X’ is less than that of the given number. Thus value at the current position depends on the following cases:

  1. If the digit of Number ‘X’ at the previous position is less than that of the given number, consider values from 0 to 9 for the current position.
  2. Else, consider values less than or equal to the value of the current position of the given number.

We don’t actually need to create a number and change its digits. Instead, we can recursively consider different digits at different positions. The considered digits can be added to a variable (say, ‘SUM’). 

For a better understanding, refer to the algorithm given below.

Algorithm

  • Create a DIGITS vector and push all the digits of input in it.
  • If ‘INDEX’ is equal to -1 (‘INDEX’  represents the current position in ‘DIGITS’), then:
    • Return ‘SUM’.
  • Set ‘LIMIT’ equal to 9. (‘LIMIT’ represents possible values at the current position).
  • If ‘IS_LAST_EQUAL’ is true, then:
    • Set LIMIT = DIGITS[INDEX ].
  • Set ‘RESULT’ equal to 0. (‘RESULT’ stores output of recursive calls).
  • Loop ‘CURRENT’ from 0 to ‘LIMIT’ (this loop tries all possible values at current positions).
    • Declare ‘IS_CURRENT_EQUAL’ (to compare current index of ‘DIGITS’ and value of ‘CURRENT’ ).
  • If DIGITS[INDEX] is equal to ‘CURRENT’ , then:
    • Set ‘IS_CURRENT_EQUAL’ to ‘IS_LAST_EQUAL’ .
  • Else:
    • Set ‘IS_CURRENT_EQUAL’ to false (to represent ‘CURRENT’ is smaller than the value present at DIGITS[‘INDEX’ ]).
  • Make a recursive call with arguments ‘INDEX’ - 1, ‘SUM’ + ‘CURRENT’ , ‘IS_CURRENT_EQUAL’ , and ‘DIGITS’ .
  • Add output of recursive call to ‘RESULT’ .
  • Return ‘RESULT’ .

Program

  • C++

C++

#include <iostream>
#include <vector>
using namespace std;

vector<int> numDigits(int num)
{

// Result vector to store the digits of the number.
vector<int> result;

// While the number has digits.
while (num)
{

// Pushing the last digit to the result vector.
result.push_back(num % 10);

// Removing the last digit from the number.
num /= 10;
}
return result;
}

long long sumOfDigits(int index, int sum, bool isLastEqual, vector<int> &digits)
{

// Base Case.
if (index == -1)
return sum;

// 'LIMIT' denotes the digits possible for current position.
int limit = 9;

/* If previous element of 'DIGITS' vector is equal to
assumed digit for previous position, 'LIMIT' is set equal to
the digit present at the current index in the 'DIGITS' vector. */
if (isLastEqual)
limit = digits[index];

int result = 0;

for (int current = 0; current <= limit; current++)
{

bool isCurrentEqual;


/* If the currently assumed digit is equal to
value in 'DIGITS' vector at current position,
the next recursive call will be notified with
the 'IS_CURRENT_EQUAL’ boolean. */

/* 'IS_CURRENT_EQUAL is true if digit at current index is equal to
the digit at current considered position.
'IS_CURRENT_EQUAL'becomes 'IS_LAST_EQUAL' in next recursive call
*/
if (digits[index] == current)
isCurrentEqual = isLastEqual;
else
isCurrentEqual = false;

// Adding the result of the recursive call to the current function call.
result += sumOfDigits(index - 1, sum + current, isCurrentEqual, digits);
}
return result;
}

int main()
{
int low, high;

cout << "Enter low: ";
cin >> low;

// Calling numDigits function to convert 'LOW' - 1 into an array of digits.
vector<int> digitsOfLow = numDigits(low - 1);

// Calling sumOfDigits function to find sum of values from 1 to 'LOW' - 1.
long long sumTillLow = sumOfDigits(digitsOfLow.size() - 1, 0, true, digitsOfLow);

cout << "Enter high: ";
cin >> high;

// Calling numDigits function to convert 'HIGH' into an array of digits.
vector<int> digitsOfHigh = numDigits(high);

// Calling sumOfDigits function to find sum of values from 1 to 'LOW' - 1.
long long sumTillHigh = sumOfDigits(digitsOfHigh.size() - 1, 0, true, digitsOfHigh);

cout << "Digit Sum: " << sumTillHigh - sumTillLow;
}

Output

output

Complexity Analysis

Time Complexity: Let’s suppose T(N) be the number of recursive calls made for a number having ‘N’ digits.

For Nth position, maximum 10 recursive calls can be made to fill the N - 1th position.

So, T(N) = 10 x T(N - 2).

Similarly, T(N - 1) = 10 x T(N - 3).

So, T(N) can be rewritten as:

T(N) = 10 x (10 x (10 x ….. T(1))).

For a number having only 1 digit, 10 different digits from 0 to 9 can be called recursively. So, for T(1) = 10.

So, T(N) = 10N, where ‘N’ is the number of digits in a number. 

The time complexity of the recursive method is exponential (10N), where ‘N’ represents the number of digits in the number.. 

Space complexity: Constant space is used in every recursive call. Total space required is  space used in one recursive call x number of recursive calls. So, the space complexity is exponential (10N), where ‘N’ represents the number of digits in the number.

Method 2: DP with Memoization

With the increase in the size of the recursive tree, the recursive function is called multiple times with the same input argument. Memoization can prune the recursive tree for our Digit DP problem by storing the results of recursive calls. All you need to do is to make some tiny changes in our recursion recipe. 

What should we memoize? Usually, the arguments that change in a recursive function are memoized. Let’s take a look at the arguments of the ‘SUM_OF_DIGITS’ function in our Method 1: Recursion section. The arguments that change with every recursive call are: ‘INDEX’, ‘SUM’, and ‘IS_EQUAL’. Create a 3-D array (say ‘MEMO’) to store values of results formed by combinations of these arguments. Every dimension of the array will represent each function. For example, MEMO[INDEX][SUM][IS_EQUAL].

What should be the size of each of the dimensions of the ‘MEMO’ array? The size analysis of each dimension is given below:

  1. Index dimension: Refer to the Constraints section in Problem Statement. The maximum value ‘LOW’ and ‘HIGH’ can have is 1018. So, the maximum number of digits possible for ‘LOW’ and ‘HIGH’ is 18. To round off, let’s set the maximum size of the ‘INDEX’ dimension to 20.
  2. Sum dimension: As we discussed above, the maximum possible indices for the input are 18. Every index can have 9 as the maximum digit sum possible. So, the last index may store the maximum value of 9 x 18 = 162. To round off, let's set the size of the ‘SUM’ dimension to 170.
  3. isEqual dimension: As ‘IS_EQUAL’ contains a boolean value, the maximum possible number of values for ‘IS_EQUAL’ is 2. Therefore, the size of the ‘IS_EQUAL’ dimension is 2.


So, the ‘MEMO’ array will have dimensions 20 x 170 x 2. To reduce the time complexity of the recursive function, we need to apply the following modifications:

  1. Before making recursive calls check if the memo array has stored the result of the given state. If the memo array has already stored the result, return the stored value. Using the memo value will avoid redundant recursive calls.
  2. Before returning to the previous recursive call, store the output of the current state to the memo array. So, the next time when the same state is called recursively, the memo will provide the stored result for the same.


Refer to the algorithm given below for a better understanding.

Algorithm

  • Declare a 3-D array ‘MEMO’ of size 20 x 170 x 2. 
  • If ‘INDEX’ is equal to -1 (Base case reached), then:
    • Return ‘SUM’.
  • If MEMO[‘INDEX’ ][‘SUM’][‘IS_LAST_EQUAL’ ] is not equal to -1, then:
    • Return MEMO[‘INDEX’ ][‘SUM’][‘IS_LAST_EQUAL’ ].
  • Set ‘LIMIT’ equal to 9. (‘LIMIT’ represents possible values at the current position).
  • If ‘IS_LAST_EQUAL’ is true, then:
    • Set ‘LIMIT’ = DIGITS[‘INDEX’ ].
  • Set ‘RESULT’ equal to 0. (‘RESULT’ stores output of recursive calls).
  • Loop ‘CURRENT’ from 0 to ‘LIMIT’. (this loop tries all possible values at current positions).
    • Declare ‘IS_CURRENT_EQUAL’ (to compare the current index of ‘DIGITS’ and the value of ‘CURRENT’ ).
  • If DIGITS[‘INDEX’ ] is equal to ‘CURRENT’ , then:
    • Set ‘IS_CURRENT_EQUAL’ to ‘IS_LAST_EQUAL’ .
  • Else:
    • Set ‘IS_CURRENT_EQUAL’ to false (to represent ‘CURRENT’ is smaller than the value present at DIGITS[‘INDEX’ ]).
  • Make a recursive call with arguments ‘INDEX’ - 1, ‘SUM’ + ‘CURRENT’ , ‘IS_CURRENT_EQUAL’ , and ‘DIGITS’ .
  • Add output of the recursive call to ‘RESULT’ .
  • If ‘IS_LAST_EQUAL’  is false, then:
    • Set MEMO[‘INDEX’ ][‘SUM’][‘IS_LAST_EQUAL’ ] = ‘RESULT’ .
  • Return ‘RESULT’ .

Program

  • C++

C++

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

int memo[20][170][2];


vector<int> numDigits(int num)
{

// Result vector to store the digits of the number.
vector<int> result;

// While the number has digits.
while (num)
{

// Pushing the last digit to the result vector.
result.push_back(num % 10);

// Removing the last digit from the number.
num /= 10;
}
return result;
}

long long sumOfDigits(int index, int sum, bool isLastEqual, vector<int> &digits)
{

// Base Case.
if (index == -1)
return sum;

if (memo[index][sum][isLastEqual] != -1)
return memo[index][sum][isLastEqual];

// 'LIMIT' denotes the digits possible for current position.
int limit = 9;

/* If previous element of 'DIGITS' vector is equal to
assumed digit for previous position, 'LIMIT' is set equal to
the digit present at the current index in the 'DIGITS' vector. */
if (isLastEqual)
limit = digits[index];

int result = 0;

for (int current = 0; current <= limit; current++)
{

bool isCurrentEqual;

/* If the currently assumed digit is equal to
value in 'DIGITS' vector at current position,
the next recursive call will be notified with
the 'IS_CURRENT_EQUAL boolean. */

/* 'IS_CURRENT_EQUAL is true if digit at current index is equal to
the digit at current considered position.
'IS_CURRENT_EQUAL 'becomes 'IS_LAST_EQUAL' in next recursive call
*/

if (digits[index] == current)
isCurrentEqual = isLastEqual;
else
isCurrentEqual = false;

// Adding the result of recursive call to current function call.
result += sumOfDigits(index - 1, sum + current, isCurrentEqual, digits);
}

// Storing the value of output in 'MEMO'.
if (!isLastEqual)
memo[index][sum][isLastEqual] = result;
return result;
}

int main()
{
int low, high;
memset(memo, -1, sizeof(memo));
cout << "Enter low: ";
cin >> low;

// Calling numDigits function to convert 'LOW' - 1 into an array of digits.
vector<int> digitsOfLow = numDigits(low - 1);

// Calling sumOfDigits function to find sum of values from 1 to 'LOW' - 1.
long long sumTillLow = sumOfDigits(digitsOfLow.size() - 1, 0, true, digitsOfLow);

cout << "Enter high: ";
cin >> high;

// Calling numDigits function to convert 'HIGH' into an array of digits.
vector<int> digitsOfHigh = numDigits(high);

// Calling sumOfDigits function to find sum of values from 1 to 'LOW' - 1.
long long sumTillHigh = sumOfDigits(digitsOfHigh.size() - 1, 0, true, digitsOfHigh);

cout << "Digit Sum: " << sumTillHigh - sumTillLow;
}

Output

output

Complexity Analysis

Time Complexity: Memoization removes the redundant recursive calls. So, every unique combination of ‘INDEX’, ‘SUM’, and ‘IS_LAST_EQUAL’ runs only once. In the worst case, all the possible combinations of ‘INDEX’, ‘SUM’, and ‘IS_LAST_EQUAL’ are fed as function arguments. So, the time complexity of the algorithm is O(INDEX x SUM x IS_LAST_EQUAL).

Space Complexity: Extra space is required to memoize the code. The size of the memo array is INDEX x SUM x IS_LAST_EQUAL. So, the space complexity is O(INDEX x SUM x IS_LAST_EQUAL).

Frequently Asked Question 

What is the digit DP?

Digit DP refers to a specific technique within dynamic programming that is used to solve problems involving numerical computations and operations on digits. It is particularly useful for tasks like counting the number of valid numbers with specific properties or optimizing numerical expressions by considering the digits.

What is the complexity of digit DP?

The complexity is typically O(N * D * M), where N is the input size, D is the digit range, and M is the number of states or subproblems.

What is the time required for dynamic programming?

The time required varies based on the problem, but dynamic programming optimizes it by breaking complex problems into smaller subproblems and reusing solutions efficiently.

Conclusion

Congratulations! You have successfully learned the Digit DP problem basics. There’s usually more than one approach to a solution. Yes, it feels sluggish to solve the same problem again and again. But, we should always try to look for more ways to solve a problem. After all, it’s an excellent way to practice more than one algorithm or technique from a single problem.

Try to memoize the code if some value is computed again and again. If the memoization is in a particular order, go for the monotonic stacks. You can practice memoization and many more cool techniques using our free practice platform Coding Ninjas Studio

Refer to our guided paths on Coding Ninjas Studio to learn more about Data Structures and AlgorithmsCompetitive Programmingetc. Enroll in our courses and refer to the mock test and problems available; look at the Top 150 Interview Puzzles interview experiences, and interview bundle for placement preparations.!

Happy Coding!.

Previous article
Introduction to Digit DP
Next article
Longest Increasing Subsequence Size
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass