Summation of a number made up of 4 5 6

Question

We are given three integers x, y and z. You have to find the sum of all numbers whose digits are made of only 4, 5 and 6, that have at most x fours in decimal representation, at most y fives in decimal representation and at most z sixes in decimal representation

I am using the concept Describe Here

My code:

// fact[i] is i!
    for(int i=0;i<=x;i++)
        for(int j=0;j<=y;j++)
            for(int k=0;k<=z;k++){

           int t = i+j+k;
           if(t==0) continue;
           long ways = fact[t-1];
           long pow = (long) Math.pow(10,t-1);
           long rep=0;
           if(i!=0){
               rep = fact[j]*fact[k];
               if(i>0) rep*=fact[i-1];

              o+= 4*pow*(ways/rep); 
           }

           if(j!=0){
               rep = fact[i]*fact[k];
               if(j>0) rep*=fact[j-1];

              o+= 5*pow*(ways/rep); 
           }

           if(k!=0){
               rep = fact[i]*fact[j];
               if(k>0) rep*=fact[k-1];

              o+= 6*pow*(ways/rep); 
           }

        }

But I am getting the wrong answer for x=1 , y=1 and z=1 i am getting 3315 while the correct answer is 3675.

Please help me find my mistake.

4+5+6+45+54+56+65+46+64+456+465+546+564+645+654=3675

Answer 1

The problem is not with your code, it's with your logic: Let S be the set of numbers consisting of only the digits 4, 5 and 6. You want to compute SUM(S). But since you're only considering the first digits of those numbers, you're in fact computing SUM(s in S, s - s % 10^floor(log10(s))).

You're doing that correctly though, because

4 + 5 + 6 + 40 + 50 + 50 + 60 + 40 + 60 + 400 + 400 
  + 500 + 500 + 600 + 600 = 3315

Long story short, all you need to do is apply user גלעד ברקן's approach below to fix your code. It will result in an O(xyz(x+y+z)) algorithm and can be improved to O(xyz) by seeing that SUM(i = 0 to t-1, 10^i) = (10^t - 1) / 9, so it's really enough to change a single line in your code:

// was: long pow = (long) Math.pow(10,t-1);
long pow = (long) (Math.pow(10,t)-1) / 9;

There is also a really simple O(xyz) time + space approach using dynamic programming that uses only a minimum of math and combinatrics: Let g(x, y, z) be tuple (count, sum) where count is the number of 4-5-6-numbers comprised of at exactly x fours, y fives and z sixes. sum is their sum. Then we have the following recurrence:

using ll=long long;
pair<ll, ll> g(int x, int y, int z) {
    if (min(x,min(y,z)) < 0)
        return {0,0};
    if (max(x,max(y,z)) == 0)
        return {1,0};
    pair<ll, ll> result(0, 0);
    for (int d: { 4, 5, 6 }) {
        auto rest = g(x - (d==4), y - (d==5), z - (d==6));
        result.first += rest.first;
        result.second += 10*rest.second + rest.first*d;
    }
    return result;
}

int main() {
    ll res = 0;
    // sum up the results for all tuples (i,j,k) with i <= x, j <= y, k <= z
    for (int i = 0; i <= x; ++i)
        for (int j = 0; j <= y; ++j)
            for (int k = 0; k <= z; ++k)
                res += g(i, j, k).second;
    cout << res << endl;
}

We can add memoization to g to avoid computing results twice, yielding a polynomial time algorithm without needing combinatoric insights.

This is easy to generalize for the case where you have more than 3 digits you can use, as demonstrated by gen-y-s's answer. It is also generalizable to cases where you have more complex restrictions on the shape of your numbers. It can even be generalized if you want to sum the numbers in a given range, by combining it with another generic DP approach.

EDIT: There's also a way to describe your function f(x, y, z) directly, the sum of 4-5-6-numbers containing at most x fours, y fives and z sixes. You need inclusion-exclusion for that. For example, for the counting part we have

c(x, y, z) = c(x-1,y,z) + c(x,y-1,z) + c(x,y,z-1) - c(x-1,y-1,z) - c(x-1,y,z-1) - c(x,y-1,z-1) + c(x-1,y-1,z-1)

It's slightly more complicated for the sums.