Number of ways N dices can make sum S

Problem: Given N dices. Each dice has A faces. Find the total number of ways these dices can make sum S when all are thrown together.

// the below code is written in C++.

#include<bits/stdc++.h> using namespace std; int main() { int s=10;  // This is the required Sum we want to generate int n=5;   // n is total number of dices. int A=6;

// A is number of faces each dice has. Each face has one unique number from 1 to A.

int i,j,k; // d[i][j] depicts number of ways i dices can make sum of j. long long int d[n+1][s+1]; // setting no. of ways for one dice to make sum 1 to A as 1. for(i=1;i<=A;i++) { d[1][i]=1; } // after A, no. of ways is 0. for(i=A+1;i<=s;i++) { d[1][i]=0; } // setting no. of ways for all dices to make sum 0 as 0. for(i=1;i<=n;i++) d[i][0]=0; for(i=2;i<=n;i++)    // for i no. of dices. {    for(j=1;j<=s;j++) //  for sum j.    {         long long int cnt=0;         for(k=1;k<=A;k++)     // for each face.         {             if(j-k>=0)             {

//  taking k for i-th dice and taking rest j-k for other (i-1) dices.                cnt+=d[i-1][j-k];                  }         }         d[i][j]=cnt;    } }

cout<<"no. of ways : "<<d[n][s]<<endl; return 0; }

Complexities :

Time complexity:    O(N*S*A)

Space complexity:   O(N*S)

Number of ways N dices can make sum S

Leave a comment