Home » Interview coding problems/challenges

# Dice throw

**Dice throw**: Here, we are going to learn about the solution of dice throw problem – which is an interview coding questions featured in any rounds of top companies.

Submitted by Radib Kar, on February 19, 2020

**Description:**

In this article, we are going to see a dynamic programing problem which can be featured in any interview rounds.

**Problem statement:**

Given **n** dice each with **m** faces, numbered from **1** to **m**, find the number of ways to get sum **X**. **X** is the summation of values on each face when all the dice are thrown.

Input: n=3 m=3 X=6 Output: Total number of ways are: 7

**Explanation:**

Total number of dices: 3 say x_{1},x_{2},x_{3}Number of faces on each dice: 3 (1 to 3) Total sum to be achieved: 6 We will write as x_{i}(j)which means face value of dice x_{i}is j So sum 6 can be achieved in following ways: 6=x_{1}(1)+x_{2}(2)+x_{3}(3) 6=x_{1}(1)+x_{2}(3)+x_{3}(2) 6=x_{1}(2)+x_{2}(2)+x_{3}(2) 6=x_{1}(2)+x_{2}(3)+x_{3}(1) 6=x_{1}(2)+x_{2}(1)+x_{3}(3) 6=x_{1}(3)+x_{2}(2)+x_{3}(3) 6=x_{1}(3)+x_{2}(3)+x_{3}(1)This are total 7 ways to achieve the sum.

**Solution Approach:**

If it was only 1 dice, then **if X<=m**, the answer would be 1 else 0. Since there is only one way to achieve the sum if possible as there is only one dice.

Now when **n**, number of dice>1, then the problem becomes a recursive one

We can think of the recursive function as **f(n,X)** where **n** is number of dice and **X** is desired sum.

A single dice has **m** choices, which means the face can have values ranging 1 to **m**

So,

Recursively we can write,

That means summation of all choices for this particular dice to have face value **1 to minimum(X, m)**

For our example case, **n=3, m=3, X=6**

So, we need to find **f(3,6)**

f(3,6)=f(2,5)+f(2,4)+f(2,3)

**f(2,5), f(2,4), f(2,3)** all are sub problems themselves which are needed to be solved further. This would generate a recursion tree.

Of course, we have base cases for single dice which is *f(1,i)=1 for i=1 to m*

But this recursion will generate many overlapping sub problems, hence, we need to convert it to dynamic programing.

1) Declare dp[n+1][x+1] similar to f(n,x). Initialize it to 0. 2) Implement the base case f(1,i) for i=1 to i minimum(m ,x) dp[1][i]=1; 3) Fill the other values as per recursion relation for i=2 to n //iterate for number of dices for j=1 to x //iterate for sums for k=1 to minimum(m ,j) //iterate for face values up to minimum(m,j),j be the subsum dp[i][j]+=dp[i-1][j-k]; end for end for end for 4) The answer is dp[n][x]

**C++ Implementation:**

#include <bits/stdc++.h> using namespace std; long long int dicethrow(int m, int n, int x) { if (m * n < x) return 0; long long dp[n + 1][x + 1]; memset(dp, 0, sizeof(dp)); //base case for (int i = 1; i <= m && i <= x; i++) dp[1][i] = 1; for (int i = 2; i <= n; i++) { //iterate for number of dices for (int j = 1; j <= x; j++) { //iterate for sums //iterate for face values up to minimum(m,j),j be the subsum for (int k = 1; k <= m & k < j; k++) { dp[i][j] += dp[i - 1][j - k]; } } } return dp[n][x]; } int main() { int n, m, x; cout << "Enter number of dices, n:\n"; cin >> n; cout << "Enter number of faces on a dice, m:\n"; cin >> m; cout << "Enter sum, X:\n"; cin >> x; cout << "Number of ways to achieve sum: " << dicethrow(m, n, x) << endl; return 0; }

**Output**

RUN 1: Enter number of dices, n: 3 Enter number of faces on a dice, m: 3 Enter sum, X: 6 Number of ways to achieve sum: 7 RUN 2: Enter number of dices, n: 3 Enter number of faces on a dice, m: 3 Enter sum, X: 12 Number of ways to achieve sum: 0

In the second output there is no way to acquire the sum which can be verified as **m*n<X**. It's better practise to keep such base case to optimize your code :)

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions