CareerCup

class DiceRoll {
	public static void main(String [] args) {
		int n = 5; // Number of dia
		int m = 5;// Number of faces in a dice 
		int X = 21;
		int [][] mem = new int[n + 1][m + 1];
		for (int i = 0; i < n + 1; i++) {
			for (int j = 0; j < m + 1; j++) {
				mem[i][j] =	 -1;
			}
		}
		System.out.println(getCount(m, n, X, mem));

	}

	public static int getCount(int m, int n, int X, int [][] mem) {
		if(n == 0 && X == 0) {
			return 1;
		}
		else {
			if (m <= 0 || n <= 0 || m * n < X) {
				return 0;
			}
			else {
				if (mem[n][m] != -1) {
					return mem[n][m];
				}
				int count = 0;
				for (int i = 0; i * m  + (n - i) <= X && n - i >= 0; i++) {
					count += getCount(m - 1, n - i, X - i * m, mem);
				}
				mem[n][m] = count;
				return count;
			}
		}
	}
}

To solve this problem we can use recursion, which will assign the highest face value to a dice, and recursively call itself, with m-1 faces (as well as lower total x-m, and n-1 dice).

#!/usr/bin/env python3

def dice(m, x, n):

  def _dice(m, x, n):
    if x==0 and n==0:
      yield curr_dice
    elif m>0:
      while x>=0 and n>=0:
        yield from _dice(m-1, x, n)
        curr_dice[m-1] += 1
        x-=m
        n-=1
      curr_dice[m-1] = 0

  curr_dice = [ 0 for i in range(m) ]
  yield from _dice(m, x, n)
  return

def main():
  m=6
  x=7
  n=2
  print(m,x,n)
  for a in dice(m,x,n):
    print(a)

if __name__ == "__main__":
    main()

If (N > m) then
If X < N then 0
If X > mN then 0
else number of ways = F ( (X-N)mod m +1 )
-- where F(n) is nth term of fibonacci sequence .

Else if (N <= m)
If X < N then 0
If X > mN then 0
else number of ways = (X-N+1)!/ ( (X-2N+2)! *N!)

As it was mentioned above there is recursive dependancy:
number of ways sum X could be calculated from n dice with m face is equal to
number of ways sum X - 1 could be calculated from n - 1 dice with m face +
number of ways sum X - 2 could be calculated from n - 1dice with m face +...
number of ways sum X - m could be calculated from n - 1 dice with m face
We use dymamic programming because of overlapping subproblems and optimal substructure.

int numberOfWays(int n, int m, int sum) {
	    	int[][] ways = new int[n + 1][sum + 1];
	    	int min = Math.min(sum,m);
	    	for(int i = 1; i<= min; i++) {
	    		ways[1][i] = 1;
	    	}
	    	
	    	for (int i  = 2; i <= n ;i++) {
	    		for (int j  = 1; j <= sum ; j++)     		
	    			 for (int k = 1; k <= m && k < j; k++)
	    				 ways[i][j] += ways[i-1][j - k];
	    		
	    	}
	    	return ways[n][sum];
	    }

Time complexity is O(sum*m*n)

You missed the part where we have to eliminate permutations
example for n=2 , m =6 and sum = 7
No of ways should be 3 ( 1,6 and 2,5 and 3,4)
but your code gives answer as 6.

You missed the part where we have to eliminate permutations
example for n=2 , m =6 and sum = 7
No of ways should be 3 ( 1,6 and 2,5 and 3,4)
but your code gives answer as 6.

pavlova wrong again....

// C#, O(NumOfDice * NumOfDice * Total)
<code><pre class="language-java">
public static string GetMutation(int[] arr, int total)
{
var sum = 0;
var str = "";
foreach (var n in arr)
{
str = str + ", " + n;
sum += n;
}
if (total == sum)
{
return str;
}
return "";
}
public static List<string> GetMutations(int NumOfFace, int NumOfDice, int Sum)
{
var permuation = new List<string>();
//no permuation
if (Sum < NumOfDice || Sum > NumOfFace*NumOfDice)
{
return permuation;
}

var getMin = Sum > NumOfFace? NumOfFace: (Sum-NumOfDice+1) ;
// var dir = new Dictionary<int, int>();
var list = new int[NumOfDice];

for (int j = 0; NumOfDice > j; j++)
{
list[j] = 1;
}
var aaa = GetMutation(list, Sum);
if (!string.IsNullOrEmpty(aaa) )
{
permuation.Add(aaa);
return permuation;
}

bool isoverFlow = false;
while (!isoverFlow)
{
aaa = GetMutation(list, Sum);
if (!string.IsNullOrEmpty(aaa))
{
permuation.Add(aaa);
}
for (int j = 0; j < NumOfDice; j++)
{

if (list[j] == getMin )
{
if (j + 1 == NumOfDice)
{
isoverFlow = true;
break;
}
list[j] = 1;
}
else
{
list[j]++;
for (int k = 0; k < j; k++)
{
list[k] = list[j];
}
break;
}

}

}
return permuation;
}
</code> </pre>

You missed the part where we have to eliminate permutations
example for n=2 , m =6 and sum = 7
No of ways should be 3 ( 1,6 and 2,5 and 3,4)
but your code gives answer as 6.