CSES Solutions – Dice Combinations
Your task is to count the number of ways to construct sum N by throwing a dice one or more times. Each throw produces an outcome between 1 and 6.
Examples:
Input: N = 3
Output: 4
Explanation: There are 4 ways to make sum = 3.
- Using 1 die {3}, sum = 3.
- Using 2 dice {1, 2}, sum = 1 + 2 = 3.
- Using 2 dice {2, 1}, sum = 2 + 1 = 3.
- Using 3 dice {1, 1, 1}, sum = 1 + 1 + 1 = 3.
Input: N = 4
Output: 8
Explanation: There are 8 ways to make sum = 4.
- Using 1 die {4}, sum = 4.
- Using 2 dice {1, 3}, sum = 1 + 3 = 4.
- Using 2 dice {2, 2}, sum = 2 + 2 = 4.
- Using 2 dice {3, 1}, sum = 3 + 1 = 4.
- Using 3 dice {1, 1, 2}, sum = 1 + 1 + 2 = 4.
- Using 3 dice {1, 2, 1}, sum = 1 + 2 + 1 = 4.
- Using 3 dice {2, 1, 1}, sum = 2 + 1 + 1 = 4.
- Using 4 dice {1, 1, 1, 1}, sum = 1 + 1 + 1 + 1 = 4.
Approach: To solve the problem, follow the below idea:
The problem can be solved using Dynamic Programming to find the number of ways to construct a particular sum. Maintain a dp[] array such that dp[i] stores the number of ways to construct sum = i. There are only 6 possible sums when we throw a dice: 1, 2, 3, 4, 5 and 6. So, if we want to find the number of ways to construct sum = S after throwing a dice, there are 6 outcomes:
- The dice outcome was 1: So, the number of ways to construct sum = S, will be equal to the number of ways to construct sum = S – 1.
- The dice outcome was 2: So, the number of ways to construct sum = S, will be equal to the number of ways to construct sum = S – 2.
- The dice outcome was 3: So, the number of ways to construct sum = S, will be equal to the number of ways to construct sum = S – 3.
- The dice outcome was 4: So, the number of ways to construct sum = S, will be equal to the number of ways to construct sum = S – 4.
- The dice outcome was 5: So, the number of ways to construct sum = S, will be equal to the number of ways to construct sum = S – 5.
- The dice outcome was 6: So, the number of ways to construct sum = S, will be equal to the number of ways to construct sum = S – 6.
This means to construct a sum S, the total number of ways will be sum of all ways to construct sum from (S – 6) to (S – 1). Now, we can construct the dp[] array as:
dp[i] = ∑(dp[i – j]), where j ranges from 1 to 6.
Step-by-step algorithm:
- Initialize a dp[] array such that dp[i] stores the number of ways we can construct sum = i.
- Initialize dp[0] = 1 as there is only 1 way to make sum = 0, that is to not throw any die at all.
- Iterate i from 1 to X and calculate number of ways to make sum = i.
- Iterate j over all possible values of the last die to make sum = i and add dp[i – j] to dp[i].
- After all the iterations, return the final answer as dp[X].
Below is the implementation of the algorithm:
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
// Function to find the number of ways to construct the
// sum N
ll solve(ll N)
{
ll mod = 1e9 + 7;
// dp[] array such that dp[i] stores the number of ways
// to construct sum = i
ll dp[N + 1] = {};
// Initialize dp[0] = 1 as there is only 1 way to
// construct sum = 0, that is to not throw any dice at
// all
dp[0] = 1;
// Iterate over all possible sums from 1 to N
for (int i = 1; i <= N; i++) {
// Iterate over all the possible values of the last die, that is from 1 to 6
for (int j = 1; j <= 6 && j <= i; j++) {
dp[i] = (dp[i] + (dp[i - j])) % mod;
}
}
// Return the number of ways to construct sum = N
return dp[N];
}
int main()
{
// Sample Input
ll N = 4;
cout << solve(N) << "\n";
}
public class DiceSumWays {
static final long MOD = 1000000007;
// Function to find the number of ways to construct the sum N
static long solve(long N) {
// dp[] array such that dp[i] stores the number of ways
// to construct sum = i
long[] dp = new long[(int) (N + 1)];
// Initialize dp[0] = 1 as there is only 1 way to
// construct sum = 0, that is to not throw any dice at all
dp[0] = 1;
// Iterate over all possible sums from 1 to N
for (int i = 1; i <= N; i++) {
// Iterate over all the possible values of the last die, that is from 1 to 6
for (int j = 1; j <= 6 && j <= i; j++) {
dp[i] = (dp[i] + dp[(int) (i - j)]) % MOD;
}
}
// Return the number of ways to construct sum = N
return dp[(int) N];
}
public static void main(String[] args) {
// Sample Input
long N = 4;
System.out.println(solve(N));
}
}
// This code is contributed by shivamgupta310570
using System;
public class GFG {
static readonly long MOD = 1000000007;
// Function to find the number of ways to construct the sum N
static long Solve(long N) {
long[] dp = new long[N + 1];
dp[0] = 1;
// Iterate over all possible sums from 1 to N
for (int i = 1; i <= N; i++) {
// Iterate over all the possible values of the last die, that is from 1 to 6
for (int j = 1; j <= 6 && j <= i; j++) {
dp[i] = (dp[i] + dp[i - j]) % MOD;
}
}
return dp[N];
}
public static void Main(string[] args) {
// Sample Input
long N = 4;
Console.WriteLine(Solve(N));
}
}
// Function to find the number of ways to construct the
// sum N
function solve(N) {
const mod = 1e9 + 7;
// dp[] array such that dp[i] stores the number of ways
// to construct sum = i
let dp = new Array(N + 1).fill(0);
// Initialize dp[0] = 1 as there is only 1 way to
// construct sum = 0, that is to not throw any dice at
// all
dp[0] = 1;
// Iterate over all possible sums from 1 to N
for (let i = 1; i <= N; i++) {
// Iterate over all the possible values of the last die, that is from 1 to 6
for (let j = 1; j <= 6 && j <= i; j++) {
dp[i] = (dp[i] + dp[i - j]) % mod;
}
}
// Return the number of ways to construct sum = N
return dp[N];
}
// Main function
function main() {
// Sample Input
let N = 4;
console.log(solve(N));
}
// Call the main function
main();
MOD = 10**9 + 7
# Function to find the number of ways to construct the sum N
def solve(N):
# dp[] array such that dp[i] stores the number of ways
# to construct sum = i
dp = [0] * (N + 1)
# Initialize dp[0] = 1 as there is only 1 way to
# construct sum = 0, that is to not throw any dice at all
dp[0] = 1
# Iterate over all possible sums from 1 to N
for i in range(1, N + 1):
# Iterate over all the possible values of the last die, that is from 1 to 6
for j in range(1, 7):
if j <= i:
dp[i] = (dp[i] + dp[i - j]) % MOD
# Return the number of ways to construct sum = N
return dp[N]
# Sample Input
N = 4
print(solve(N))
Output
8
Time Complexity: O(N), where N is the sum which we need to construct.
Auxiliary Space: O(N)
Contact Us