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.
