This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses 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) All of the mentioned

View Answer

Explanation: All of the mentioned methods 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

View Answer

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. 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

Explanation: 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

View Answer

Explanation: 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) none of the mentioned

View Answer

Explanation: 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

View Answer

Explanation: 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

View Answer

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. 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) none of the mentioned

View Answer

Explanation: The line arr[num_of_dice][S] completes the above code.

9. What is time complexity of the above 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?

a) O(n*f)

b) O(f*s)

c) O(n*s)

d) O(n*f*s)

View Answer

Explanation: The time complexity of the above dynamic programming implementation is O(n*f*s).

10. What is space complexity of the above 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?

a) O(n*f)

b) O(f*s)

c) O(n*s)

d) O(n*f*s)

View Answer

Explanation: The space complexity of the above dynamic programming implementation is O(n*s).

11. 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

Explanation: 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<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

Explanation: The value stored in arr[2][2] is 1.

13. 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

Explanation: The minimum possible sum is 4. So, the output for sum = 3 is 0.

14. 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

Explanation: The output of the above code is 4.

**Sanfoundry Global Education & Learning Series – Data Structure.**

To practice all areas of Data Structure, __here is complete set of 1000+ Multiple Choice Questions and Answers__.