Dice throw ( DSA INTERVIEW PREPARATION PROBLEMS AND SOLUTIONS ) ~ Multiplex Coder

Asked in AMAZON and MICROSOFT

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.

Example 1:

Input:
M = 6, N = 3, X = 12
Output:
25
Explanation:
There are 25 total ways to get
the Sum 12 using 3 dices with
faces from 1 to 6.

Example 2:

Input:
M = 2, N = 3, X = 6
Output:
1
Explanation:
There is only 1 way to get
the Sum 6 using 3 dices with
faces from 1 to 2. All the
dices will have to land on 2.

Your Task:
You don't need to read input or print anything. Your task is to complete the function noOfWays() which takes 3 Integers M,N and X as input and returns the answer.

Expected Time Complexity: O(M*N*X)
Expected Auxiliary Space: O(N*X)

Constraints:
1 <= M,N,X <= 50

Code:

// C++ program to find number of ways to get sum 'x' with 'n'

// dice where every dice has 'm' faces

#include <iostream>

#include <string.h>

using namespace std;

// The main function that returns number of ways to get sum 'x'

// with 'n' dice and 'm' with m faces.

int findWays(int m, int n, int x)

{

// Create a table to store results of subproblems. One extra

// row and column are used for simpilicity (Number of dice

// is directly used as row index and sum is directly used

// as column index). The entries in 0th row and 0th column

// are never used.

int table[n + 1][x + 1];

memset(table, 0, sizeof(table)); // Initialize all entries as 0

// Table entries for only one dice

for (int j = 1; j <= m && j <= x; j++)

table[1][j] = 1;

// Fill rest of the entries in table using recursive relation

// i: number of dice, j: sum

for (int i = 2; i <= n; i++)

for (int j = 1; j <= x; j++)

for (int k = 1; k <= m && k < j; k++)

table[i][j] += table[i-1][j-k];

/* Uncomment these lines to see content of table

for (int i = 0; i <= n; i++)

{

for (int j = 0; j <= x; j++)

cout << table[i][j] << " ";

cout << endl;

} */

return table[n][x];

}

// Driver program to test above functions

int main()

{

cout << findWays(4, 2, 1) << endl;

cout << findWays(2, 2, 3) << endl;

cout << findWays(6, 3, 8) << endl;

cout << findWays(4, 2, 5) << endl;

cout << findWays(4, 3, 5) << endl;

return 0;

}

Dice throw ( DSA INTERVIEW PREPARATION PROBLEMS AND SOLUTIONS )

Related Post