Do you think IIT Guwahati certified course can help you in your career?
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.
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.
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:
Using eq(3) and eq(2) in eq(1), Sum(LOW, HIGH) can be rewritten as:
Sum(LOW, HIGH) = 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:
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.
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);
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:
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.
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.
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:
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.
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:
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 */
// 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);
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.
85+ registered 