Count ways to obtain given sum by repeated throws of a dice

19 June 2025

0

Given an integer N, the task is to find the number of ways to get the sum N by repeatedly throwing a dice.

Examples:

Input: N = 3
Output: 4
Explanation:
The four possible ways to obtain N are:

1 + 1 + 1

1 + 2

2 + 1

3

Input: N = 2
Output: 2
Explanation:
The two possible ways to obtain N are:

1 + 1

2

Recursive Approach: The idea is to iterate for every possible value of dice to get the required sum N. Below are the steps:

Let findWays() be the required answer for sum N.
The only numbers obtained from the throw of dice are [1, 6], each having equal probability in a single throw of dice.
Therefore, for every state, recur for the previous (N – i) states (where 1 ? i ? 6). Therefore, the recursive relation is as follows:

findWays(N) = findWays(N – 1) + findWays(N – 2) + findWays(N – 3) + findWays(N – 4) + findWays(N – 5) + findWays(N – 6)

Below is the implementation of the above approach:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the number of ways
// to get the sum N with throw of dice
int findWays(int N)
{
    // Base Case
    if (N == 0) {
        return 1;
    }
 
    // Stores the count of total
    // number of ways to get sum N
    int cnt = 0;
 
    // Recur for all 6 states
    for (int i = 1; i <= 6; i++) {
 
        if (N - i >= 0) {
 
            cnt = cnt
                  + findWays(N - i);
        }
    }
 
    // Return answer
    return cnt;
}
 
// Driver Code
int main()
{
    int N = 4;
 
    // Function call
    cout << findWays(N);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Function to find the number of ways
// to get the sum N with throw of dice
static int findWays(int N)
{
     
    // Base Case
    if (N == 0)
    {
        return 1;
    }
 
    // Stores the count of total
    // number of ways to get sum N
    int cnt = 0;
 
    // Recur for all 6 states
    for(int i = 1; i <= 6; i++)
    {
        if (N - i >= 0) 
        {
            cnt = cnt + 
                  findWays(N - i);
        }
    }
 
    // Return answer
    return cnt;
}
 
// Driver Code
public static void main(String[] args)
{
    int N = 4;
 
    // Function call
    System.out.print(findWays(N));
}
}
 
// This code is contributed by 29AjayKumar 

Python3

# Python3 program for the above approach
 
# Function to find the number of ways
# to get the sum N with throw of dice
def findWays(N):
     
    # Base case
    if (N == 0):
        return 1
 
    # Stores the count of total
    # number of ways to get sum N
    cnt = 0
 
    # Recur for all 6 states
    for i in range(1, 7):
        if (N - i >= 0):
            cnt = cnt + findWays(N - i)
 
    # Return answer
    return cnt
     
# Driver Code
if __name__ == '__main__':
     
    N = 4
 
    # Function call
    print(findWays(N))
 
# This code is contributed by mohit kumar 29

C#

// C# program for 
// the above approach 
using System;
class GFG{
 
// Function to find the number of ways
// to get the sum N with throw of dice
static int findWays(int N)
{
  // Base Case
  if (N == 0)
  {
    return 1;
  }
 
  // Stores the count of total
  // number of ways to get sum N
  int cnt = 0;
 
  // Recur for all 6 states
  for(int i = 1; i <= 6; i++)
  {
    if (N - i >= 0) 
    {
      cnt = cnt + findWays(N - i);
    }
  }
 
  // Return answer
  return cnt;
}
 
// Driver Code
public static void Main()
{
  int N = 4;
 
  // Function call
  Console.Write(findWays(N));
}
}
 
// This code is contributed by sanjoy_62

Javascript

<script>
 
// JavaScript program for the above approach
 
 
// Function to find the number of ways
// to get the sum N with throw of dice
function findWays(N)
{
    // Base Case
    if (N == 0) {
        return 1;
    }
 
    // Stores the count of total
    // number of ways to get sum N
    var cnt = 0;
 
    // Recur for all 6 states
    for (var i = 1; i <= 6; i++) {
 
        if (N - i >= 0) {
 
            cnt = cnt
                  + findWays(N - i);
        }
    }
 
    // Return answer
    return cnt;
}
 
// Driver Code
var N = 4;
 
// Function call
document.write( findWays(N));
 
 
</script>

Output:

Time Complexity: O(6^N)
Auxiliary Space: O(1)

Dynamic Programming Approach: The above recursive approach needs to be optimized by dealing with the following overlapping subproblems:

Overlapping Subproblems:
Partial recursion tree for N = 8:

Optimal Substructure: As for every state, recurrence occurs for 6 states, so the recursive definition of dp(N) is the following:

dp[N] = dp[N-1] + dp[N-2] + dp[N-3] + dp[N-4] + dp[N-5] + dp[N-6]

Follow the steps below to solve the problem:

Initialize an auxiliary array dp[] of size N + 1 with initial value -1, where dp[i] stores the count of ways of having sum i.
The base case while solving this problem is if N is equal to 0 in any state, the result to such a state is 1.
If for any state dp[i] is not equal to -1, then this value as this substructure is already beed calculated.

Top-Down Approach: Below is the implementation of the Top-Down approach:

C++

// C++ Program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate the total
// number of ways to have sum N
int findWays(int N, int dp[])
{
    // Base Case
    if (N == 0) {
        return 1;
    }
 
    // Return already stored result
    if (dp[N] != -1) {
 
        return dp[N];
    }
 
    int cnt = 0;
 
    // Recur for all 6 states
    for (int i = 1; i <= 6; i++) {
 
        if (N - i >= 0) {
            cnt = cnt
                  + findWays(N - i, dp);
        }
    }
 
    // Return the result
    return dp[N] = cnt;
}
 
// Driver Code
int main()
{
    // Given sum N
    int N = 4;
 
    // Initialize the dp array
    int dp[N + 1];
 
    memset(dp, -1, sizeof(dp));
 
    // Function Call
    cout << findWays(N, dp);
 
    return 0;
}

Java

// Java Program for 
// the above approach
import java.util.*;
class GFG{
 
// Function to calculate the total
// number of ways to have sum N
static int findWays(int N, int dp[])
{
    // Base Case
    if (N == 0) 
    {
        return 1;
    }
 
    // Return already 
    // stored result
    if (dp[N] != -1) 
    {
        return dp[N];
    }
 
    int cnt = 0;
 
    // Recur for all 6 states
    for (int i = 1; i <= 6; i++) 
    {
        if (N - i >= 0) 
        {
            cnt = cnt + 
                  findWays(N - i, dp);
        }
    }
 
    // Return the result
    return dp[N] = cnt;
}
 
// Driver Code
public static void main(String[] args)
{
    // Given sum N
    int N = 4;
 
    // Initialize the dp array
    int []dp = new int[N + 1];
 
    for (int i = 0; i < dp.length; i++)
        dp[i] = -1;
 
    // Function Call
    System.out.print(findWays(N, dp));
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python3 Program for the 
# above approach
 
# Function to calculate 
# the total number of ways 
# to have sum N
def findWays(N, dp):
 
    # Base Case
    if (N == 0):
        return 1
    
    # Return already 
    # stored result
    if (dp[N] != -1):
        return dp[N]
 
    cnt = 0
 
    # Recur for all 6 states
    for i in range (1, 7):
        if (N - i >= 0):
            cnt = (cnt +
                   findWays(N - i, dp))
 
    # Return the result
    dp[N] = cnt
    return dp[N]
 
# Driver Code
if __name__ == "__main__":
 
    # Given sum N
    N = 4
 
    # Initialize the dp array
    dp = [-1] * (N + 1)
 
    # Function Call
    print(findWays(N, dp))
 
# This code is contributed by Chitranayal

C#

// C# Program for 
// the above approach
using System;
class GFG{
 
// Function to calculate the total
// number of ways to have sum N
static int findWays(int N, int []dp)
{
  // Base Case
  if (N == 0) 
  {
    return 1;
  }
 
  // Return already stored result
  if (dp[N] != -1) 
  {
    return dp[N];
  }
 
  int cnt = 0;
 
  // Recur for all 6 states
  for (int i = 1; i <= 6; i++) 
  {
    if (N - i >= 0) 
    {
      cnt = cnt + findWays(N - i, dp);
    }
  }
 
  // Return the result
  return dp[N] = cnt;
}
 
// Driver Code
public static void Main(String[] args)
{
  // Given sum N
  int N = 4;
 
  // Initialize the dp array
  int []dp = new int[N + 1];
 
  for (int i = 0; i < dp.Length; i++)
    dp[i] = -1;
 
  // Function Call
  Console.Write(findWays(N, dp));
}
}
  
// This code is contributed by Rajput-Ji

Javascript

<script>
// Javascript Program for
// the above approach
 
// Function to calculate the total
// number of ways to have sum N
function findWays(N,dp)
{
    // Base Case
    if (N == 0)
    {
        return 1;
    }
  
    // Return already
    // stored result
    if (dp[N] != -1)
    {
        return dp[N];
    }
  
    let cnt = 0;
  
    // Recur for all 6 states
    for (let i = 1; i <= 6; i++)
    {
        if (N - i >= 0)
        {
            cnt = cnt +
                  findWays(N - i, dp);
        }
    }
  
    // Return the result
    return dp[N] = cnt;
}
 
// Driver Code
let N = 4;
  
// Initialize the dp array
let dp = new Array(N + 1);
 
for (let i = 0; i < dp.length; i++)
    dp[i] = -1;
 
// Function Call
document.write(findWays(N, dp));
 
 
// This code is contributed by unknown2108
</script>

Output:

Time Complexity: O(N)
Auxiliary Space: O(N)

Bottom-Up Approach: Below is the implementation of the Bottom-up Dynamic Programming approach:

C++

// C++ Program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate the total
// number of ways to have sum N
void findWays(int N)
{
    // Initialize dp array
    int dp[N + 1];
 
    dp[0] = 1;
 
    // Iterate over all the possible
    // intermediate values to reach N
    for (int i = 1; i <= N; i++) {
 
        dp[i] = 0;
 
        // Calculate the sum for
        // all 6 faces
        for (int j = 1; j <= 6; j++) {
 
            if (i - j >= 0) {
                dp[i] = dp[i] + dp[i - j];
            }
        }
    }
 
    // Print the total number of ways
    cout << dp[N];
}
 
// Driver Code
int main()
{
    // Given sum N
    int N = 4;
 
    // Function call
    findWays(N);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
  
class GFG{
  
// Function to calculate the total
// number of ways to have sum N
static void findWays(int N)
{
     
    // Initialize dp array
    int []dp = new int[N + 1];
  
    dp[0] = 1;
  
    // Iterate over all the possible
    // intermediate values to reach N
    for(int i = 1; i <= N; i++)
    {
        dp[i] = 0;
  
        // Calculate the sum for
        // all 6 faces
        for(int j = 1; j <= 6; j++) 
        {
            if (i - j >= 0)
            {
                dp[i] = dp[i] + dp[i - j];
            }
        }
    }
  
    // Print the total number of ways
    System.out.print(dp[N]);
}
  
// Driver Code
public static void main(String[] args)
{
     
    // Given sum N
    int N = 4;
  
    // Function call
    findWays(N);
}
}
  
// This code is contributed by Amit Katiyar

Python3

# Python3 program for 
# the above approach
 
# Function to calculate the total
# number of ways to have sum N
def findWays(N):
   
    # Initialize dp array
    dp = [0] * (N + 1);
    dp[0] = 1;
 
    # Iterate over all the 
    # possible intermediate 
    # values to reach N
    for i in range(1, N + 1):
        dp[i] = 0;
 
        # Calculate the sum for
        # all 6 faces
        for j in range(1, 7):
            if (i - j >= 0):
                dp[i] = dp[i] + dp[i - j];
 
    # Print total number of ways
    print(dp[N]);
 
# Driver Code
if __name__ == '__main__':
   
    # Given sum N
    N = 4;
 
    # Function call
    findWays(N);
 
# This code is contributed by 29AjayKumar

C#

// C# program for 
// the above approach
using System;
class GFG{
  
// Function to calculate the total
// number of ways to have sum N
static void findWays(int N)
{
  // Initialize dp array
  int []dp = new int[N + 1];
 
  dp[0] = 1;
 
  // Iterate over all the possible
  // intermediate values to reach N
  for(int i = 1; i <= N; i++)
  {
    dp[i] = 0;
 
    // Calculate the sum for
    // all 6 faces
    for(int j = 1; j <= 6; j++) 
    {
      if (i - j >= 0)
      {
        dp[i] = dp[i] + dp[i - j];
      }
    }
  }
 
  // Print the total number of ways
  Console.Write(dp[N]);
}
  
// Driver Code
public static void Main(String[] args)
{
  // Given sum N
  int N = 4;
 
  // Function call
  findWays(N);
}
} 
 
// This code is contributed by 29AjayKumar

Javascript

<script>
 
// JavaScript program for the above approach
 
// Function to calculate the total
// number of ways to have sum N
function findWays(N)
{
    // Initialize dp array
    let dp = new Array(N + 1);
   
    dp[0] = 1;
   
    // Iterate over all the possible
    // intermediate values to reach N
    for(let i = 1; i <= N; i++)
    {
        dp[i] = 0;
   
        // Calculate the sum for
        // all 6 faces
        for(let j = 1; j <= 6; j++)
        {
            if (i - j >= 0)
            {
                dp[i] = dp[i] + dp[i - j];
            }
        }
    }
   
    // Print the total number of ways
    document.write(dp[N]);
}
 
// Driver Code
 // Given sum N
let N = 4;
   
// Function call
findWays(N);
 
 
// This code is contributed by patel2127
 
</script>

Output:

Time Complexity: O(N)
Auxiliary Space: O(N)

Efficient Approach: space optimization O(1)

To optimize the space complexity of the previous solution by using only an array of size 6 instead of an array of size N+1 to store the values of dp. We only need to store the values for the last 6 values of dp at any point in time.

Implementation Steps:

Create an array DP if size 6 instead of size N because we need only the previous 6 computations to get the current value.
Initialize DP with base case dp[0] = 1.
Iterate over subproblems and get the current value from previous solutions of subproblems stored in DP.
At the last return, the final answer is stored in dp[N%6]. ( n%6 ) to compute only the last 6 values.

Implementation:

C++

// C++ program for above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate the total
// number of ways to have sum N
void findWays(int N)
{
    // Initialize dp array
    int dp[6];
 
    dp[0] = 1;
 
    // Iterate over all the possible
    // intermediate values to reach N
    for (int i = 1; i <= N; i++) {
        int sum = 0;
 
        // Calculate the sum for
        // all 6 faces
        for (int j = 1; j <= 6; j++) {
 
            if (i - j >= 0) {
                sum += dp[(i-j)%6];
            }
        }
 
        // Store the sum for the current i
        dp[i%6] = sum;
    }
 
    // Print the total number of ways
    cout << dp[N%6];
}
 
// Driver Code
int main()
{
    // Given sum N
    int N = 4;
 
    // Function call
    findWays(N);
 
    return 0;
}
 
// this code is contributed by bhardwajji

Java

import java.util.*;
 
public class DiceSum {
 
    // Function to calculate the total
    // number of ways to have sum N
    public static void findWays(int N) {
         
        // Initialize dp array
        int[] dp = new int[6];
 
        dp[0] = 1;
 
        // Iterate over all the possible
        // intermediate values to reach N
        for (int i = 1; i <= N; i++) {
            int sum = 0;
 
            // Calculate the sum for
            // all 6 faces
            for (int j = 1; j <= 6; j++) {
 
                if (i - j >= 0) {
                    sum += dp[(i-j)%6];
                }
            }
 
            // Store the sum for the current i
            dp[i%6] = sum;
        }
 
        // Print the total number of ways
        System.out.println(dp[N%6]);
    }
 
    // Driver Code
    public static void main(String[] args) {
        // Given sum N
        int N = 4;
 
        // Function call
        findWays(N);
    }
}

Python3

# Python program for above approach
 
# Function to calculate the total
# number of ways to have sum N
def findWays(N):
    # Initialize dp array
    dp = [0] * 6
 
    dp[0] = 1
 
    # Iterate over all the possible
    # intermediate values to reach N
    for i in range(1, N+1):
        sum = 0
 
        # Calculate the sum for
        # all 6 faces
        for j in range(1, 7):
 
            if i - j >= 0:
                sum += dp[(i-j)%6]
 
        # Store the sum for the current i
        dp[i%6] = sum
 
    # Print the total number of ways
    print(dp[N%6])
 
# Driver Code
if __name__ == '__main__':
    # Given sum N
    N = 4
 
    # Function call
    findWays(N)

C#

using System;
 
public class MainClass
{
    public static void Main()
    {
        int N = 4;
 
        // Initialize dp array
        int[] dp = new int[6];
 
        dp[0] = 1;
 
        // Iterate over all the possible
        // intermediate values to reach N
        for (int i = 1; i <= N; i++)
        {
            int sum = 0;
 
            // Calculate the sum for
            // all 6 faces
            for (int j = 1; j <= 6; j++)
            {
                if (i - j >= 0)
                {
                    sum += dp[(i-j)%6];
                }
            }
 
            // Store the sum for the current i
            dp[i%6] = sum;
        }
 
        // Print the total number of ways
        Console.WriteLine(dp[N%6]);
    }
}

Javascript

let N = 4;
 
// Initialize dp array
let dp = new Array(6).fill(0);
 
dp[0] = 1;
 
// Iterate over all the possible
// intermediate values to reach N
for (let i = 1; i <= N; i++) {
let sum = 0;
 
// Calculate the sum for
// all 6 faces
for (let j = 1; j <= 6; j++) {
if (i - j >= 0) {
sum += dp[(i - j) % 6];
}
}
 
// Store the sum for the current i
dp[i % 6] = sum;
}
 
// Print the total number of ways
console.log(dp[N % 6]);

Output

Time Complexity: O(N)
Auxiliary Space: O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

Count ways to obtain given sum by repeated throws of a dice

C++

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

LEAVE A REPLY Cancel reply

Most Popular

EDITOR PICKS

POPULAR POSTS

POPULAR CATEGORY

ABOUT US

FOLLOW US