Some problems ask to find how many numbers from A to B have a certain property, if the problem of finding how many numbers of k (0-9) digits have that property can be solved using a function F(k,property) in O(H) and when you update the left of a number the property can be updated in O(S) then there is a solution for the problem in O(H * S * log10^2(n)).

Let M(x) the amount of numbers less than x that have that property. Then M(B + 1) — M(A) is the solution to our problem, or M(B) — M(A) + h where (h = 1 if B have the property, else h = 0) To find M(x) we need to make a few observations. A number x less than y iff the length of x is less than the length of y or if they have equal length and there is a digit x[i] < y[i] and for all digits j < i this holds x[j] = y[j], that is ,they are equal from left to right until a digit i where x[i] < y[i], when this happens then all digits y[j] j > i can be in the range(0-9) and then F(k,property) can be used. We can use this to find all the numbers less than x having the desired property.

sol  = 0
remain = lengthof(x)
// we find the digit where they first differ x[i] < y[i] and for all digits j < i x[j] = y[j]
for each digit x[i] of x from left to right{
    remain--;
    // now we find all the digits that can be at y[i] and are less than x[i]
    for each digit d from 0 to x[i] - 1{
        property' = (property if digit d replaced digit x[i]) 
        sol += F(remain,property')
    }
    update property after deletion of digit x[i]
}

Here I have a sample C++ code to solve the following problem How many integers in the interval [A, B] are there such that the sum of their digits is S

#define ll long long
bool mem[N][N];
ll D[N][N];
// this is the function F(k,property)
ll F(int dig,int sum){
	if(dig == 0)
		return (ll)(sum  == 0);
	if(mem[dig][sum])
		return D[dig][sum];
	mem[dig][sum] = 1;
	ll ret = 0LL;
	for(int i = 0;i<=9;i++)
		ret += F(dig - 1,sum - i);
	D[dig][sum] = ret;
	return ret;
}

// this is M(x)
ll solve(ll x){
	ll ret = 0;
	sprintf(cad,"%lld",x);
	int len = strlen(cad);
        //sum is the desired property
	int sum = s;
	int qued = len;
        // we find the digit where they first differ x[i] < y[i] and for all digits j < i x[j] = y[j]
	for(int i = 0;i < len;i++){
		qued--;
		int d = cad[i] - '0';
                // now we find all the digits that can be at y[i] and are less than x[i]
		for(int j = 0;j <d;j++){
                        //sum - j = property'
			if(sum - j >= 0){
				ret += F(qued,sum - j);
			}
		}
                //update property after deletion of digit x[i]
		sum -= d;
	}
	return ret;
}


//this is the solution to the problem
sol = solve(b + 1) - solve(a);

Some problems to solve

and many other you can find anywhere

Comments (32)

Show archived | Write comment?

ylguirola

11 years ago, # |

it is good

→ Reply

jlcastrillon

← Rev. 6 →

these are other similar problems http://lightoj.com/volume_showproblem.php?problem=1205 http://www.spoj.com/problems/NUMTSN/

abhishekg

10 years ago, # ^ |

@jlcastrillon can you please check my code what's wrong in it for http://www.spoj.com/problems/NUMTSN/ problem.... it is giving TLE

include<bits/stdc++.h>

using namespace std;

long long int mod=1000000007;

long long int d[51][51][51][51];

bool mem[51][51][51][51];

int len;

long long int f(int i, int three, int six, int nine, int lo, char *cad) {

if (i == len)
{

    if(three==six && six==nine)
                    return 1;
            else
                    return 0;
}


long long int ret = 0;

int dig;


if (lo) {
    if (mem[i][three][six][nine]) {
       return d[i][three][six][nine];
    } else {
       mem[i][three][six][nine] = 1;
       long long int r = 0;
       for (dig = 0; dig <= 9; ++dig) {
         if(dig==3)
                                    r=(r+f(i + 1,three+1, six,nine, lo, cad))%mod;
                            else if(dig==6)
                                    r=(r+f(i + 1,three, six+1,nine, lo, cad))%mod;
                            else if(dig==9)
                                    r=(r+f(i + 1,three, six,nine+1 , lo, cad))%mod;
                            else
                                    r=(r+f(i + 1,three, six,nine, lo, cad))%mod;
       }
       d[i][three][six][nine] = r%mod;
       return r%mod;
    }
}

int limit;
limit = cad[i] - '0';

for (dig = 0; dig <= limit; ++dig) {
                            if(dig==3)
                                    ret=(ret+f(i + 1,three+1, six,nine, (lo || (dig < (cad[i] - '0'))), cad))%mod;
                            else if(dig==6)
                                    ret=(ret+f(i + 1,three, six+1,nine, (lo || (dig < (cad[i] - '0'))), cad))%mod;
                            else if(dig==9)
                                    ret=(ret+f(i + 1,three, six,nine+1 , (lo || (dig < (cad[i] - '0'))), cad))%mod;
                            else
                                    ret=(ret+f(i + 1,three, six,nine, (lo || (dig < (cad[i] - '0'))), cad))%mod;
}
return ret%mod;

}

long long int solve(char *x) { len = strlen(x);

memset(d, 0, sizeof(d));

memset(mem, 0, sizeof(mem));

return f(0, 0, 0,0, 0, x);

char aa[51];

char bb[51];

int check(char *x) { int a=0,b=0,c=0,i,j,k;

k=strlen(x);

    for(i=0;i<k;i++){

            if(x[i]=='3')
                    a++;

            else if(x[i]=='6')
                    b++;

            else if(x[i]=='9')
                    c++;

    }

    if(a==b && b==c)
            return 1;
    else
            return 0;

int main() { int t;

long long int sol;

     char r;

    scanf("%d",&t);

    while(t--){

            scanf("%s",&aa);

            scanf("%c",&r);

            scanf("%s",&bb);

            scanf("%c",&r);

            sol = (solve(bb) - solve(aa))%mod;

            sol= sol + check(aa);

            printf("%lld\n",sol%mod);

    }
    return 0;

← Rev. 4 →

accepted now :)

xdavewk

← Rev. 2 →

I'm trying to solve the same problem and getting TLE. What did you improve in your code? I don't know what else to do :s

This is the main function of my code. Could you please help me?

int f(int i, int tres, int seis, int nueve, bool menor)
{
	int piv = max(tres, max(seis, nueve));

	if ( piv-nueve + piv-seis + piv-tres > n-i or (piv == 0 and n-i < 3) )
		return 0;

	if (i == n)
		return tres == seis and tres == nueve and tres > 0;

	if (dp[i][tres][seis][nueve][menor] != -1)
		return dp[i][tres][seis][nueve][menor];

	int res = 0, end = menor ? 9 : x[i] - '0';
	For(d, 0, end+1)
		res = ( res + f( i+1, tres + (d == 3), seis + (d == 6), nueve + (d == 9), menor | (d < x[i] - '0') ) ) % MOD;

	return dp[i][tres][seis][nueve][menor] = res;
}

ABHISHEK004

i also have the same problem

saurabh060792

You don't need 5 dimensional dp(it had given me tle when I used 4D dp). Try solving it by combinatorics.

mjnovice

9 years ago, # ^ |

solved! :) AC! Thanks a lot people for the valuable insights.

pk842

6 years ago, # ^ |

can you please share your accepted code?

HandIeNeeded

Google Code jam 2014 Round1 B Problem B is a good problem of this kind.^_^

niklasb

Indeed, I wrote about the solution here

r-neo

10 years ago, # |

Hey nice article , can you please give link to some working code of the problem . like I have lot of trouble writing the F(k, property) in different cases...

chrome

For example: Solution for Last contest 431D

thanks for the reply , but in the above case the sum (s) is given , so we are able to get the difference and calculate it, but in some cases , like where 1. some property of the difference b/w the sum of the even place digits and odd place digits must have some property like being prime number or diff should be 1 .

Is there any tutorial which tells how to formulate 3-Dimensional dp for it.

vipul.jain

int d[10][50][50];
bool mem[10][50][50];
int len;

int f(int i, int sum_odd, int sum_even, int lo, const string& cad)
{
	if (i == len) {
		return (sum_even - sum_odd == 1);
	}
	int ret = 0;
	int dig;
	
	if (lo) { 
		if (mem[i][sum_odd][sum_even]) {
			return d[i][sum_odd][sum_even];
		} else { 
			mem[i][sum_odd][sum_even] = 1;
			int r = 0;
			for (dig = 0; dig <= 9; ++dig) {
				if ((len - i) % 2 == 0) {
					r += f(i + 1, sum_odd, sum_even + dig, lo, cad);
				} else {
					r += f(i + 1, sum_odd + dig, sum_even, lo, cad);
				}
			}
			d[i][sum_odd][sum_even] = r;
			return r;
		}
	}
	
	int limit;
	limit = cad[i] - '0';
	
	for (dig = 0; dig <= limit; ++dig) {
		if ((len - i) % 2 == 0) {
			ret += f(i + 1, sum_odd, sum_even + dig, (lo || (dig < (cad[i] - '0'))), cad);
		} else {
			ret += f(i + 1, sum_odd + dig, sum_even, (lo || (dig < (cad[i] - '0'))), cad);
		}
	}
	return ret;
}

int solve (int x)
{
	string cad;
	cad = NumtoString(x);
	len = cad.length();
	memset(d, 0, sizeof(d));
	memset(mem, 0, sizeof(mem));
	return f(0, 0, 0, 0, cad);
}

my implementation is guided by this post

http://stackoverflow.com/questions/22394257/how-to-count-integers-between-large-a-and-b-with-a-certain-property/22394258#22394258

flickr

How it is covering all the numbers less than 123 (say)? first we choose 1 and varied it from 0- 0 -> it covers 000- 099 then we choose 2 and varied it from 0- 1 -> it covers 000- 019. please give some explanation!

for 123 when changing 1 it covers from 000 to 099 when changing 2 it covers from 100 to 119 when changing 3 it covers from 120 to 122

to calculate how many numbers less than X have certain property iterate through all possible positions where a number Y may differ for the first time when compared with X and through all possible digits for that position. you can easily notice that the rest(all the digits to the right of that position ) may take values from 0 to 9, then then if you have a function(almost always solvable by dp) to calculate how many numbers with n(any amount) of digits have certain property(for example a sum equal to S) then your problem is solved.

@jlcastrillon nice article...

but can you please tell me how to find count of numbers between a and b which contains 0 as their digit... i am not able to get this with above idea, it becomes very complex in case of leading zeroes

please give some explanation as i am having lot of trouble with this ...

waiting for ur reply

first of all find a dp solution to the problem when all digits can be form 0 to 9 and having a fixed number of digits. Then when calculating for a number X how many numbers are less than it and cantain at least one zero, don't take into account the zero digit when changing the value of the first digit this will give you as a solution all the numbers that contain at least one zero with the same number of digits than X and dont't contain leading zeros, then add to the solution how many numbers with less digits than X are there that contain at least one zero and don't contain leading zeroes. Have in mind that you need a special case dp that tells you the solution when the first digit cannot be zero for the second part of the solution.

I write a blog on my website discussing the skill to solve problems of this kind with a contest I created consisting of almost every problem mentioned in this blog or comment. It's a pity that I wrote it in Chinese. So if you are interested in it and you can read Chinese, CLICK!

Thank you very much. I cant read Chinese, but i was able to find the code of the problem i was getting TLE and learned about using a - b instead of a and b and check for a - b = 0 instead of a = b.