Hola People, This is my Third blog and second Technical Blog. Its about Digit-DP. For anyone who is doing competitive programming for more than a year must have encountered a question like Given two numbers [ L , R ] find number of integers in this range which satisfy a particular property. The First question of this type which i came across of this type was Sum of Range . I couldn’t think of a solution , finally googled it and found this Explanation1-GFG Explanation-Stackoverflow_2 . Both involved more of maths and less of logical code. It took me some time to understand the concept, wrote it down in my code-book but still wasn’t satisfied as it wasn’t something which i could freely apply or modify and I am not good with numbers . Guess what there is a top down-approach which can solve not just this problem but all the problems which have a similar property. That is exactly what we will be discussing in this post.
The property
” Given a Range Find number/sum/(or any other associative mathematical operation) of integers which satisfy a given property that are within the range [L,R]”
The approach
- The First problem that we need to solve is how to get integers which satisfy the given range. suppose our range is from 10^6 to 10^18. One solution is to loop from 10^6 to 10^18 and evaluate each integer but it will require operations in order of 10^18 which is not possible to evaluate in 1 second. So lets think of an alternative.
- Lets consider our final solution as F ( L , R ) . Lets break this function into two parts F( L , R ) = F( R , 0 ) – F ( L – 1 , 0 )
yipee! now we don’t have to worry about the left boundary as it is always zero. We just need to get our right limits right and we are done for this part. - If we think a little we can see that this range will include all those integers which have number of digits less than n. That is any two digit number will be included whenever our right limit has 3 or more digits.
- Now problem arises in case when we want to form a number which has n digits and is less than our right limit. This is slightly tricky. Consider Our right limit to be RnRn-1Rn-2……..R1R0 Where Rn is the most significant digit and R0 is the least significant digit in decimal representation. Lets start building our number from most significant integer i.e First add Hn then Hn-1 and finally Ho. Constaint on Hn is that it would always be less ‘Rn‘ otherwise number formed would always be greater than the upper limit. This gives us the start of our implementation. for ( int start = 1 ; start <= Rn ; start ++ )
- Now we need to think about how to add Hn-1 to H0. The claim is “we can put any digit from 0 to 9 at position k-i where i ∈ [ 1 , k ] if we have already added a digit Hk that was strictly less than Rk at kth position else we can only add digit which ∈ [ 0 , Rk ]“.
Well :p ! That was my reaction. Lets make things simple to understand. Consider this example.
Suppose our upper limit was 5872 and Hn or first digit we added was 4 then Hn-1 can take any value from 0 to 9 [40..] – [49..] and number will always remain smaller than 5872 Second case is if Hn was equal to 5 then Hn-1 can take values only from 0..8 that is we can try from [50..] to [58..] and we can simply ignore [59..] as it would always be greater than our upper limit. This is exactly what the claim meant 🙂
Implementation
Well Talking is done lets get to some serious code. Lets discuss the problem with which we started Sum of Range . It would be best if you try to code it yourself. For all the lazy people I have commented everything in the code so that its self – explanatory
#include
using namespace std;
#define REP(i, a, b) for (int i = a; i <= b; i++)
#define FOR(i, n) for (int i = 0; i length of the number formed
// j - > "small" discussed later
// k - > required to store presum
void calc( Int a , Int b )
{
while( a ) { a= a/10 ; na++ ; }
while( b ) { b= b/10 ; nb++ ; }
}
Int compute ( Int presum , Int digit )
{
return presum + digit ; // function to compute sub-result
}
int cnt = 0 ;
Int solve( string& a , Int idx , Int limit , Int small , Int presum )
{
// limit is the number of digits in number in decimal format
// idx -> denotes that we are building the ith digit, it can go from 0 ( Most Significant digit ) to limit - 1 ( Least significant digit )
// small is the constraint
// small = 0 indicates that we can take any value from 0 to 9 as we have taken a smaller digit below
// small = 1 indicates that we can only take value from 0 to a[idx]
// small = 2 indicates that we cannot form a n digit smaller than right limit so we are going to make only numbers that have less than n digits
if( idx == limit-1 && small == 2 ) // since if small == 2 we have to stop at n - 1 can't go forward
return 0 ;
if( idx >= limit ) // base condition if idx > number of digits
return 0 ;
if( dp[idx][small][presum] != -1 )return dp[idx][small][presum] ;
// memo table to store the result of computations so that if we encounter a same state again we can just return this
Int loop = 9 ; // setting the upper limit of loop to 9
Int num = a[idx] - '0' ; // digit at ith index
Int sum = 0 ;
Int i = 0 ; // start of loop
if( idx == 0 )i = 1 ; // first digit of number cannot be zero
// just checking the conditions in the loop
for( ; i num && idx != limit-1 ) sum = sum + compute( presum , i ) + solve( a , idx + 1 , limit , 2 , presum + i ) ;
if( i < num ) sum = sum + compute( presum , i ) + solve( a , idx + 1 , limit , 0 , presum + i ) ;
if( i == num ) sum = sum + compute( presum , i ) + solve( a , idx + 1 , limit , 1 , presum + i ) ;
}
}
dp[ idx ][ small ][presum] = sum ; // storing the value in table
return dp[ idx ][ small ][presum] ;
}
INITIALISATION
int main ( )
{
na = nb = 0 ;
Int a , b ;
cin >> a >> b ;
if( a == -1 && b == -1 ) break ;
calc( a - 1, b );
string bs = to_string( b ) ;
string as = to_string( a -1 ) ;
Int g ,s ;
memset(dp,-1,sizeof(dp)) ;
g = solve( bs , 0 , nb ,1, 0 ) ;
memset(dp,-1,sizeof(dp)) ;
s = solve ( as , 0, na,1 , 0 );
cout<<g-s<<endl;
}
Second problem We would be discussing is RAONE . Again we all we need to do is change compute function according to problem rest everything remains same. Here is the code and Gist_Link
Int na , nb ;
Int dp[ 10 ][ 3 ][ 100 ][ 100 ] ;
void calc( Int a , Int b )
{
while( a ) { a= a/10 ; na++ ; }
while( b ) { b= b/10 ; nb++ ; }
}
int cnt = 0 ;
Int check( Int idx , Int even_sum , Int odd_sum )
{
if( (idx&1LL) == 0 )swap( even_sum , odd_sum ) ;
if( even_sum - odd_sum != 1 )return 0 ;
//cout<<even_sum<<" "<<odd_sum<= limit )
return 0 ;
if( dp[idx][small][even_sum][odd_sum] != -1 )return dp[idx][small][even_sum][odd_sum] ;
Int loop = 9 ;
Int num = a[idx] - '0' ;
Int sum = 0 ;
Int i = 0 ;
if( idx == 0 )i = 1 ;
for( ; i num && idx != limit-1 ) sum = sum + check(idx,tpeven ,tpodd ) + solve( a , idx + 1 , limit , 2 , tpeven , tpodd ) ;
if( i < num ) sum = sum + check(idx,tpeven ,tpodd ) + solve( a , idx + 1 , limit , 0 , tpeven , tpodd) ;
if( i == num ) sum = sum + check(idx,tpeven ,tpodd) + solve( a , idx + 1 , limit , 1 , tpeven , tpodd) ;
}
}
dp[ idx ][ small ][even_sum][odd_sum] = sum ;
return dp[ idx ][ small ][even_sum][odd_sum] ;
}
The third problem LUCIFER , the problem is same as before and uses similar thinking just need to modify the compute/check function a bit. Gist_Link
Int na , nb ;
Int dp[ 10 ][ 3 ][ 100 ][ 100 ] ;
Int a[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97} ;
bool Hash[100] = {false} ;
void calc( Int a , Int b )
{
while( a ) { a= a/10 ; na++ ; }
while( b ) { b= b/10 ; nb++ ; }
}
int cnt = 0 ;
Int check( Int idx , Int even_sum , Int odd_sum )
{
if( (idx&1LL) == 0 )swap( even_sum , odd_sum ) ;
if( even_sum - odd_sum < 0 || Hash[ even_sum - odd_sum ] == false )return 0 ;
//cout<<even_sum<<" "<<odd_sum<= limit )
return 0 ;
if( dp[idx][small][even_sum][odd_sum] != -1 )return dp[idx][small][even_sum][odd_sum] ;
Int loop = 9 ;
Int num = a[idx] - '0' ;
Int sum = 0 ;
Int i = 0 ;
if( idx == 0 )i = 1 ;
for( ; i num && idx != limit-1 ) sum = sum + check(idx,tpeven ,tpodd ) + solve( a , idx + 1 , limit , 2 , tpeven , tpodd ) ;
if( i < num ) sum = sum + check(idx,tpeven ,tpodd ) + solve( a , idx + 1 , limit , 0 , tpeven , tpodd) ;
if( i == num ) sum = sum + check(idx,tpeven ,tpodd) + solve( a , idx + 1 , limit , 1 , tpeven , tpodd) ;
}
}
dp[ idx ][ small ][even_sum][odd_sum] = sum ;
return dp[ idx ][ small ][even_sum][odd_sum] ;
}
The last problem and probably the best of them came in recent Walmart hiring challenge DIGIT-MINI-MAX but again with little modification in the check function you can solve this problem. Gist_link
Int na , nb ;
Int dp[ 13 ][ 3 ][ 10 ][ 10 ][ 10 ][ 100 ] ;
void calc( Int a , Int b )
{
while( a ) { a= a/10 ; na++ ; }
while( b ) { b= b/10 ; nb++ ; }
}
int cnt = 0 ;
Int check( Int idx, Int a , Int b , Int c )
{
if( idx a && b > c ) return 1 ;
if( b < a && b = limit )
return 0 ;
if( dp[idx][small][a][b][c][presum] != -1 )return dp[idx][small][a][b][c][presum] ;
Int loop = 9 ;
Int num = str[idx] - '0' ;
Int sum = 0 ;
Int i = 0 ;
if( idx == 0 )i = 1 ;
for( ; i num && idx != limit-1 ) sum = sum + presum + check(idx, b , c , i ) + solve( str , idx + 1 , limit , 2 , b , c , i,presum + check(idx, b , c , i ) ) ;
if( i < num ) sum = sum + presum + check(idx, b , c , i ) + solve( str , idx + 1 , limit , 0 , b , c , i,presum + check(idx, b , c , i )) ;
if( i == num ) sum = sum + presum + check(idx, b , c , i ) + solve( str , idx + 1 , limit , 1 , b , c , i,presum + check(idx, b , c , i )) ;
}
}
dp[idx][small][a][b][c][presum] = sum ;
return dp[idx][small][a][b][c][presum] ;
}
I know it was a long and tiring post but just hope that you learned something new 🙂 . Thanks bye bye ta-ta.
In learning you will teach, and in teaching you will learn – Phil Collins
saisumit 
Good Work
LikeLiked by 1 person
Thanks 🙂
LikeLike
Hey, that was an awesome tutorial. Thanks!
LikeLiked by 1 person
Thanks 🙂
LikeLike
what is the use of
if(idx==0) i=1;
what does idx==0 represent most significant or least significant ?
and what is their in the for loop
for( ?; i ? num && idx != limit-1 )
LikeLiked by 1 person
Pingback: Recent Topics – Champions_Unknown
Learning DIGIT DP from your blog. Thanks!
LikeLiked by 1 person
Very nice blog. Keep up good work!
LikeLiked by 1 person