Engineering Questions with Answers - Multiple Choice Questions
Data Structure MCQ – Dice Throw Problem
1 - Question
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
View Answer
Answer: d
Explanation: Brute force, Recursion and Dynamic Programming can be used to solve the dice throw problem.
2 - Question
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
View Answer
Answer: b
Explanation: Each die can take f values and there are n dice. So, the total number of permutations is f*f*f…n times.
3 - Question
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
View Answer
Answer: c
Explanation: The total number of permutations that can be obtained is 6 * 6 * 6 = 216.
4 - Question
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
View Answer
Answer: c
Explanation: The sum of 11 can be achieved when the dice show {6, 5} or {5, 6}.
5 - Question
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
View Answer
Answer: c
Explanation: The sum will be minimum when all the faces show a value 1. The sum in this case will be n.
6 - Question
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
View Answer
Answer: d
Explanation: The sum will be maximum when all the faces show a value f. The sum in this case will be n*f.
7 - Question
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
View Answer
Answer: a
Explanation: 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 - Question
Consider the following dynamic programming implementation of the dice throw problem:
#include<stdio.h> 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]
View Answer
Answer: a
Explanation: The line arr[num_of_dice][S] completes the above code.
9 - Question
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<stdio.h> 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)
View Answer
Answer: d
Explanation: The time complexity of the above dynamic programming implementation is O(n*f*s).
10 - Question
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<stdio.h> 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)
View Answer
Answer: c
Explanation: The space complexity of the above dynamic programming implementation is O(n*s).
11 - Question
What is the output of the following code?
#include<stdio.h> 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
View Answer
Answer: a
Explanation: The output of the above code is 10.
12 - Question
What will be the value stored in arr[2][2] when the following code is executed?
#include<stdio.h> 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
View Answer
Answer: b
Explanation: The value stored in arr[2][2] is 1.
13 - Question
What is the output of the following code?
#include<stdio.h> 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
View Answer
Answer: a
Explanation: The minimum possible sum is 4. So, the output for sum = 3 is 0.
14 - Question
What is the output of the following code?
#include<stdio.h> 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
View Answer
Answer: c
Explanation: The output of the above code is 4.