It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened,
visit the help center.
Closed 8 years ago.
Given n dice, each of 'a' sides and a sum b, return the number of ways in which the sum b can be obtained. How can you reduce the time complexity and space complexity?
This was asked in a Google interview and I am unsure of the answer.
This is asking you to find the number of ways to write b as a sum of n positive integers. The answer is the number of compositions of b into n parts, which is (b-1 choose n-1).
Now if we take into account the constraint that the size of the parts is limited to a, the problem gets a little more interesting. I recommend using generating functions for this. The answer will be the coefficient of x^b in the product (x+x^2+...+x^a)^n. Why? Because for each die (the singular of dice), you have a number between 1 and a, and this is represented by the exponent of x. When you take one x^i from each of the n terms, this is equivalent to the number i coming up on that die. The sum of the exponents must be the sum you are after, namely b.
We can even simplify the problem a bit using the multinomial theorem which states:
(x + x^2 + ... + x^a)^n = sum_{k1+k2+...+ka=n} (n multichoose k1,k2,...,ka) x^{k1+2*k2+...+a*ka}
where all ki >= 0. So the answer is that the number of ways is
sum_{k1+k2+...+ka=n & k1+2*k2+...+a*ka=b} (n multichoose k1,k2,...,ka)
I would have an array hits[max + 1] which counts the number of possible combination for each value. max is n * a and of course hits[0] to hits[n - 1] will remain empty.
The dumb way would be to do n for-loop (one for each die) and register a hit in hits for the current sum of the dice.
The less dumb way is to use a bit of combinatorics, where I write out the number of combinations for each ordered shuffle:
there is 1 combination of 1111 (sum = 4)
there are 4 combination of 1112 (sum = 5)
there are 4 combination of 1113 (sum = 6)
...
there are 4 * 3 / 2 combinations of 1123 (sum = 7)
...
there are 4 * 3 * 2 combinations of 1234 (sum = 10)
...
there is 1 combination of aaaa (sum = n * a)
You need to spend much less times in the for-loops than the dumb solution.
You get many hits for each iteration instead of just one hit with the dumb method.
Those for-loops just move the (n - 1) partition separations over (1, 2, 3, 4, ..., a).
The separations can be on the same spot (e.g. they are all between 1 and 2 for the case 1111), but you must not have a separation below 1 or above a.
Assuming a is large enough( to be specific a>=b-n), this boils down to
x1+x2+x3+...+xn=b
which is the typical problem of distributing 'b' candies amongst 'n' kids.
if you want to avoid 0 faced dies it should be easy to see that
(y1+1)+(y2+1)...+(yn+1)=b
y1+y2+...+yn=b-n
so a general solution to
z1+z2+...zk=n is
C(n+k-1,k-1)
EDIT after reciving several downvotes:
Assuming we have limit on 'a' i.e. b-n>a,
we can formulate it as a DP problem where
dp[k][j] is no. of ways to get a sum of j using dices 1 to k inclusive
dp[1][j] is 0 if j>a or j==0 else 1
then we can have evaluate following relation
from k = 2 to n
from j = 1 to b
from x = 1 to a
dp[k][j] += dp[k-1][j-x] where x is from 1 to a at max and x<j
and answer should be dp[n][b]
The storage if of order n*b and runtime O(n*b*a)
