Dice Throws

Hard
0/120
Average time to solve is 35m
16 upvotes
Asked in companies
MicrosoftDisney + HotstarShareChat

Problem statement

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?
Detailed explanation ( Input/output format, Notes, Images )
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
Sample input 1 :
3
2 5 10
1 6 9
2 6 8
Sample output 1 :
1
0
5
Explanation of sample input 1 :
For test case 1 :  
We are given 2 dice with 5 faces numbered 1, 2, 3, 4 and 5.
The only possible way of getting a sum of 10 is when both the die face 5. Hence, the answer is 1.  

For test case 2 :
We are given 1 dice with 6 faces numbered 1, 2, 3, 4, 5 and 6.
There is no possible way of getting a sum of 9 with a single die having all the faces less than 9. Hence, the answer is 0. 

For test case 3 :
We are given 2 dice with 6 faces numbered 1, 2, 3, 4, 5 and 6.
The possible ways are [{2, 6}, {3, 5}, {4, 4}, {5, 3}, {6, 2}]. Hence, the answer is 5.
Sample input 2 :
2
6 3 8  
2 2 3
Sample output 2 :
21
0
Hint

The very first approach can be to try all the combinations of all the faces for all the dice and maintain the count of those combinations that sum up to S.

Approaches (4)
Brute force
  1. The idea is to use recursion to reduce the big problem into several small subproblems.
  2. 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.
  3. 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. 
     
  4. Return answer.
Time Complexity

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.

Space Complexity

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.

Code Solution
(100% EXP penalty)
Dice Throws
Full screen
Console