Data Structure Multiple Choice Questions on “Dice Throw Problem”.
1. You are given n dice each having f faces. You have to find the number of ways in which a sum of S can be achieved. This is the dice throw problem. Which of the following methods can be used to solve the dice throw problem?
a) Brute force
b) Recursion
c) Dynamic programming
d) Brute force, Recursion and Dynamic Programming
Answer: d
Clarification: Brute force, Recursion and Dynamic Programming can be used to solve the dice throw problem.
2. You have n dice each having f faces. What is the number of permutations that can be obtained when you roll the n dice together?
a) n*n*n…f times
b) f*f*f…n times
c) n*n*n…n times
d) f*f*f…f times
Answer: b
Clarification: Each die can take f values and there are n dice. So, the total number of permutations is f*f*f…n times.
3. You have 3 dice each having 6 faces. What is the number of permutations that can be obtained when you roll the 3 dice together?
a) 27
b) 36
c) 216
d) 81
Answer: c
Clarification: The total number of permutations that can be obtained is 6 * 6 * 6 = 216.
4. You have 2 dice each of them having 6 faces numbered from 1 to 6. What is the number of ways in which a sum of 11 can be achieved?
a) 0
b) 1
c) 2
d) 3
Answer: c
Clarification: The sum of 11 can be achieved when the dice show {6, 5} or {5, 6}.
5. There are n dice with f faces. The faces are numbered from 1 to f. What is the minimum possible sum that can be obtained when the n dice are rolled together?
a) 1
b) f
c) n
d) n*f
Answer: c
Clarification: The sum will be minimum when all the faces show a value 1. The sum in this case will be n.
6. There are n dice with f faces. The faces are numbered from 1 to f. What is the maximum possible sum that can be obtained when the n dice are rolled together?
a) 1
b) f*f
c) n*n
d) n*f
Answer: d
Clarification: The sum will be maximum when all the faces show a value f. The sum in this case will be n*f.
7. There are 10 dice having 5 faces. The faces are numbered from 1 to 5. What is the number of ways in which a sum of 4 can be achieved?
a) 0
b) 2
c) 4
d) 8
Answer: a
Clarification: Since there are 10 dice and the minimum value each die can take is 1, the minimum possible sum is 10. Hence, a sum of 4 cannot be achieved.
8. Consider the following dynamic programming implementation of the dice throw problem:
#include
int get_ways(int num_of_dice, int num_of_faces, int S)
{
int arr[num_of_dice + 1][S + 1];
int dice, face, sm;
for(dice = 0; dice <= num_of_dice; dice++)
for(sm = 0; sm <= S; sm++)
arr[dice][sm] = 0;
for(sm = 1; sm <= S; sm++)
arr[1][sm] = 1;
for(dice = 2; dice <= num_of_dice; dice++)
{
for(sm = 1; sm <= S; sm++)
{
for(face = 1; face <= num_of_faces && face < sm; face++)
arr[dice][sm] += arr[dice - 1][sm - face];
}
}
return _____________;
}
int main()
{
int num_of_dice = 3, num_of_faces = 4, sum = 6;
int ans = get_ways(num_of_dice, num_of_faces, sum);
printf("%d",ans);
return 0;
}
Which of the following lines should be added to complete the above code?
a) arr[num_of_dice][S]
b) arr[dice][sm]
c) arr[dice][S]
d) arr[S][dice]
Answer: a
Clarification: The line arr[num_of_dice][S] completes the above code.
9. What is time complexity of the following dynamic programming implementation of the dice throw problem where f is the number of faces, n is the number of dice and s is the sum to be found?
#include
int get_ways(int num_of_dice, int num_of_faces, int S)
{
int arr[num_of_dice + 1][S + 1];
int dice, face, sm;
for(dice = 0; dice <= num_of_dice; dice++)
for(sm = 0; sm <= S; sm++)
arr[dice][sm] = 0;
for(sm = 1; sm <= S; sm++)
arr[1][sm] = 1;
for(dice = 2; dice <= num_of_dice; dice++)
{
for(sm = 1; sm <= S; sm++)
{
for(face = 1; face <= num_of_faces && face < sm; face++)
arr[dice][sm] += arr[dice - 1][sm - face];
}
}
return arr[num_of_dice][S];
}
int main()
{
int num_of_dice = 3, num_of_faces = 4, sum = 6;
int ans = get_ways(num_of_dice, num_of_faces, sum);
printf("%d",ans);
return 0;
}
a) O(n*f)
b) O(f*s)
c) O(n*s)
d) O(n*f*s)
Answer: d
Clarification: The time complexity of the above dynamic programming implementation is O(n*f*s).
10. What is space complexity of the following dynamic programming implementation of the dice throw problem where f is the number of faces, n is the number of dice and s is the sum to be found?
#include
int get_ways(int num_of_dice, int num_of_faces, int S)
{
int arr[num_of_dice + 1][S + 1];
int dice, face, sm;
for(dice = 0; dice <= num_of_dice; dice++)
for(sm = 0; sm <= S; sm++)
arr[dice][sm] = 0;
for(sm = 1; sm <= S; sm++)
arr[1][sm] = 1;
for(dice = 2; dice <= num_of_dice; dice++)
{
for(sm = 1; sm <= S; sm++)
{
for(face = 1; face <= num_of_faces && face < sm; face++)
arr[dice][sm] += arr[dice - 1][sm - face];
}
}
return arr[num_of_dice][S];
}
int main()
{
int num_of_dice = 3, num_of_faces = 4, sum = 6;
int ans = get_ways(num_of_dice, num_of_faces, sum);
printf("%d",ans);
return 0;
}
a) O(n*f)
b) O(f*s)
c) O(n*s)
d) O(n*f*s)
Answer: c
Clarification: The space complexity of the above dynamic programming implementation is O(n*s).
11. What is the output of the following code?
#include
int get_ways(int num_of_dice, int num_of_faces, int S)
{
int arr[num_of_dice + 1][S + 1];
int dice, face, sm;
for(dice = 0; dice <= num_of_dice; dice++)
for(sm = 0; sm <= S; sm++)
arr[dice][sm] = 0;
for(sm = 1; sm <= S; sm++)
arr[1][sm] = 1;
for(dice = 2; dice <= num_of_dice; dice++)
{
for(sm = 1; sm <= S; sm++)
{
for(face = 1; face <= num_of_faces && face < sm; face++)
arr[dice][sm] += arr[dice - 1][sm - face];
}
}
return arr[num_of_dice][S];
}
int main()
{
int num_of_dice = 3, num_of_faces = 4, sum = 6;
int ans = get_ways(num_of_dice, num_of_faces, sum);
printf("%d",ans);
return 0;
}
a) 10
b) 12
c) 14
d) 16
Answer: a
Clarification: The output of the above code is 10.
12. What will be the value stored in arr[2][2] when the following code is executed?
#include
int get_ways(int num_of_dice, int num_of_faces, int S)
{
int arr[num_of_dice + 1][S + 1];
int dice, face, sm;
for(dice = 0; dice <= num_of_dice; dice++)
for(sm = 0; sm <= S; sm++)
arr[dice][sm] = 0;
for(sm = 1; sm <= S; sm++)
arr[1][sm] = 1;
for(dice = 2; dice <= num_of_dice; dice++)
{
for(sm = 1; sm <= S; sm++)
{
for(face = 1; face <= num_of_faces && face < sm; face++)
arr[dice][sm] += arr[dice - 1][sm - face];
}
}
return arr[num_of_dice][S];
}
int main()
{
int num_of_dice = 3, num_of_faces = 4, sum = 6;
int ans = get_ways(num_of_dice, num_of_faces, sum);
printf("%d",ans);
return 0;
}
a) 0
b) 1
c) 2
d) 3
Answer: b
Clarification: The value stored in arr[2][2] is 1.
13. What is the output of the following code?
#include
int get_ways(int num_of_dice, int num_of_faces, int S)
{
int arr[num_of_dice + 1][S + 1];
int dice, face, sm;
for(dice = 0; dice <= num_of_dice; dice++)
for(sm = 0; sm <= S; sm++)
arr[dice][sm] = 0;
for(sm = 1; sm <= S; sm++)
arr[1][sm] = 1;
for(dice = 2; dice <= num_of_dice; dice++)
{
for(sm = 1; sm <= S; sm++)
{
for(face = 1; face <= num_of_faces && face < sm; face++)
arr[dice][sm] += arr[dice - 1][sm - face];
}
}
return arr[num_of_dice][S];
}
int main()
{
int num_of_dice = 4, num_of_faces = 6, sum = 3;
int ans = get_ways(num_of_dice, num_of_faces, sum);
printf("%d",ans);
return 0;
}
a) 0
b) 1
c) 2
d) 3
Answer: a
Clarification: The minimum possible sum is 4. So, the output for sum = 3 is 0.
14. What is the output of the following code?
#include
int get_ways(int num_of_dice, int num_of_faces, int S)
{
int arr[num_of_dice + 1][S + 1];
int dice, face, sm;
for(dice = 0; dice <= num_of_dice; dice++)
for(sm = 0; sm <= S; sm++)
arr[dice][sm] = 0;
for(sm = 1; sm <= S; sm++)
arr[1][sm] = 1;
for(dice = 2; dice <= num_of_dice; dice++)
{
for(sm = 1; sm <= S; sm++)
{
for(face = 1; face <= num_of_faces && face < sm; face++)
arr[dice][sm] += arr[dice - 1][sm - face];
}
}
return arr[num_of_dice][S];
}
int main()
{
int num_of_dice = 2, num_of_faces = 6, sum = 5;
int ans = get_ways(num_of_dice, num_of_faces, sum);
printf("%d",ans);
return 0;
}
a) 2
b) 3
c) 4
d) 5
Answer: c
Clarification: The output of the above code is 4.