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

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

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

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

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

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

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

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]

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)

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)

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

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

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

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