Dice throw
You are given D dice, each having F faces numbered 1 to F, both inclusive. The task is to find the possible number of ways to roll the dice together such that the sum of face-up numbers equal the given target S.

Note :

As the answer can be large, return your answer modulo 10^9 + 7.

Follow Up :

Can you solve this using not more than O(S) extra space?

Input format :

The first line of input contains an integer T denoting the number of test cases. The first and the only line of every test case contains 3 integers D, F and S representing the number of dices, the number of faces on each die and the target sum respectively.

Output format :

For each test case, print the number of ways to get the sum S in a separate line.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1

Question

Dice throw

You are given D dice, each having F faces numbered 1 to F, both inclusive. The task is to find the possible number of ways to roll the dice together such that the sum of face-up numbers equal the given target S.

Note :

As the answer can be large, return your answer modulo 10^9  + 7.

Follow Up :

Can you solve this using not more than O(S) extra space?

Input format :

The first line of input contains an integer T denoting the number of test cases. 

The first and the only line of every test case contains 3 integers D, F and S representing the number of dices, the number of faces on each die and the target sum respectively.

Output format :

For each test case, print the number of ways to get the sum S in a separate line.

Note :

 You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 5    
1 <= D, F <= 50
1 <= S <= 10^3

Time limit: 1 sec

Accepted Answer

I used dp to solve this problem with the Number of dice directly used as row index and the sum is directly used as the column index. In the end, I returned the last element of dp table.

Accepted Answer

Brute force

The idea is to use recursion to reduce the big problem into several small subproblems.
We will call a helper function that returns us the number of combinations that sum upto S and store it in a variable say answer.
The algorithm for the helper function will be as follows:

Int helper(D, F, S):
A. If D as well as S becomes 0, return 1.
B. If D becomes 0 or S becomes negative, return 0.
C. Initialise a count variable say finalCount with 0.
D. For i = 1 to F:
Call helper function for D-1 and S-i, add it to the finalCount.
finalCount += helper(D-1, F, S-i)
E. Return finalCount.
Return answer.

Space Complexity: O(1)Explanation:

O(D) per test case where D is the number of dice.

In the worst case, extra space will be used by the recursion stack as there can be a maximum of D number of recursive calls at a time in the recursive stack.

Time Complexity: O(1)Explanation:

O(F ^ D) per test case where F is the number of faces and D is the number of dice.

In the worst case, we are making F calls for each recursive call. Thus, We are making F ^ D calls for D dice.

Accepted Answer

Memoization

Let’s understand by an example

Suppose we have 3 dice each with 6 faces and we have to find the number of ways to achieve the sum 8.

The below figure shows some of the recursive calls are made for the given problem.

Note: Subproblem {a,b,c} means a problem with ‘a’ dice each with ‘b’ faces and ‘c’ is the desired sum.

As we can see, some subproblems are called multiple times.

For example, the subproblem {1,6,5} is called 2 times, {1,6,3} is called 4 times and {1,6,1} is called 6 times.

That’s why we are storing the solved subproblems in a lookup table so that we don’t have to solve them again. Whenever a call is made to the solved subproblem, we will directly return the answer of that subproblem stored in the lookup table.

Approach:

The idea is to use memoization.
Create a 2D lookup table to store the solutions to the subproblems where lookUp[i][j] denotes the possible number of ways to get sum j with i number of dice/die.
Initialize the table by -1.
Now, we call a helper function that returns us the number of combinations using D dice with F faces that sum up to S and store it in a variable say answer.
The algorithm for the helper function will be as follows:

Int helper(D, F, S):
A. If D, as well as S, becomes 0, return 1.
B. If D becomes 0 or S becomes negative, return 0.
C. If lookUp[D][S] is not equal to -1, return lookUp[D][S].
D. Initialise a count variable say finalCount with 0.
E. For i = 1 to F:
Call helper function for D-1 and S-i, add it to the finalCount.
finalCount += helper(D-1, F, S-i)
F. Update lookUp[D][S] with finalCount.
G. Return lookUp[D][S]
Return answer.

Space Complexity: O(n^2)Explanation:

O(D * S) per test case where D is the number of dice and S is target sum.

In the worst case, we are using a memoization table of size D*S.

Time Complexity: OtherExplanation:

O(D * F * S) per test case where D, F and S are the number of dice, number of faces and target sum respectively.

In the worst case, the 2-D array dp stores the results for all the subproblems, we can conclude that we will not have more than D*S subproblems and for each recursive call, we will iterate F times. therefore O(D * F * S).

Accepted Answer

DP

The idea is to create a 2-D DP with row size D+1 and column size S+1.
Initially all the elements of the DP table will be 0.
Now, the value DP[i][j] means the possible number of combinations with i dice and j sum. Thus, initialise DP[0][0] as 1.
The detailed algorithm to fill the DP table will be as follows:
1. Loop 1: For i = 1 to D:
2. Loop 2: For j = 1 to S:
3. Loop 3: For k = 1 to F:
  if( j-k >= 0 ), DP[i][j] += DP[i-1][j-k]
Return DP[D][S].

Let us understand the above algorithm in detail with an example:
For the test case where D = 3, F = 6 and S = 4

We will create a DP table with 4 (D + 1) rows and 5 columns (S +1) with all elements as 0.
Now, for 0 number of Die, we have 1 way for getting 0 sum. Thus, DP[0][0] should be 1.

In the next step when we are at DP[1][1], this means that we have to fill the number of ways to get a sum of 1(S) with 1(D) die. This can be found by letting a number 1 on 1 die and fetching the possible number of combinations for 0(D-1) die having 0(S-1) sum which is at DP[0][0]. Thus, DP[1][1] becomes 1.
Now, let's take number 2 on 1 die and fetch the possible number of combinations for 0(D-1) die having -1 (S-2) sum. Note that negative sum is not possible to achieve and thus we stop traversing further.
Similarly, for DP[1][2] will be DP[0][1] + DP[0][0] and so on DP[1][4] will be DP[0][3] + DP[0][2] + DP[0][1] + DP[0][0].

The table will be:

In the next iteration, we are at DP[2][1], this means that we have to fill the number of ways to get a sum of 1(S) with 2(D) dice. This can be found by letting a number 1 on 1 die and fetching the possible number of combinations for 1(D-1) die having 0(S-1) sum i.e DP[1][0]. Thus, DP[2][1] becomes 0.
Now, let's take number 2 on 1 die and fetch the possible number of combinations for 1(D-1) die having -1 (S-2) sum. Note that negative sum is not possible to achieve and thus we stop traversing further.

We will notice:

DP[2][2] = DP[1][1] + DP[1][0]

DP[2][3] = DP[1][2] + DP[1][1] + DP[1][0]

DP[2][4] = DP[1][3] + DP[1][2] + DP[1][1] + DP[1][0]

The table becomes:

Similarly, the final table will be:

Space Complexity: O(n^2)Explanation:

O(D * S) per test case where D is the number of dice and S is target sum.

In the worst case, we are using a DP table of size D*S.

Time Complexity: OtherExplanation:

O(D * F * S) per test case where D, F and S are the number of dice, number of faces and target sum respectively.

In the worst case, we will be using 3 nested loops. Thus, O(D * F * S).

Accepted Answer

Optimized DP

The idea is to create a 1-D DP of size S+1.
Initially, all the elements of the DP table will be 0.
We can make only S = 0 with 0 dice, so dp[0] = 1,
The detailed algorithm to fill the DP table will be as follows:
1. Loop 1: For i = 1 to D:
2. Loop 2: For j = S to 1:
3. Loop 3: For k = 1 to F:
  if( j-k >= 0 ), DP[j] += DP[j-k]
Return DP[D][S].

Space Complexity: O(n)Explanation:

O(S) per test case where S is the target sum.

In the worst case, we are using a DP array of size S+1.

Time Complexity: OtherExplanation:

O(D * F * S) per test case where D, F and S are the number of dice, number of faces and target sum respectively.

In the worst case, we will be using 3 nested loops. Thus, O(D * F * S).

You are given D dice, each having F faces numbered 1 to F, both inclusive. The task is to find the possible number of ways to roll the dice together such that the sum of face-up numbers equal the given target S.

Note :

Follow Up :

Input format :

Output format :

Note :

Constraints :

Top Microsoft Corporation Software Developer Intern interview questions & answers

Popular interview questions of Software Developer Intern

Top HR questions asked in Microsoft Corporation Software Developer Intern