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
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With