Ways to sum to N using Natural Numbers up to K with repetitions allowed

0 0 7 minutes read

Given two integers N and K, the task is to find the total number of ways of representing N as the sum of positive integers in the range [1, K], where each integer can be chosen multiple times.

Examples:

Input: N = 8, K = 2
Output: 5
Explanation: All possible ways of representing N as sum of positive integers less than or equal to K are:

{1, 1, 1, 1, 1, 1, 1, 1}, the sum is 8.

{2, 1, 1, 1, 1, 1, 1}, the sum is 8.

{2, 2, 1, 1, 1, 1}, the sum is 8.

2, 2, 2, 1, 1}, the sum is 8.

{2, 2, 2, 2}}, the sum is 8.

Therefore, the total number of ways is 5.

Input: N = 2, K = 2
Output: 2

Naive Approach: The simplest approach to solve the given problem is to generate all possible combinations of choosing integers over the range [1, K] and count those combinations whose sum is N.

Implementaion :

C++

//C++ program for above approach
 
#include <bits/stdc++.h>
using namespace std;
 
 
// Function that return Ways to sum to N using
// Natural Numbers up to K with repetitions allowed
int NumberOfways(int N, int K) {
     
    // Base case
    if (N == 0) return 1;
    if (N < 0 || K <= 0) return 0;
     
    // including and not including K in sum
    return NumberOfways(N - K, K) + NumberOfways(N, K - 1);
}
 
 
// Driver code
int main() {
    int N = 8;
    int K = 2;
     
    // function call
    cout << NumberOfways(N, K) << endl;
    return 0;
}
 
// this code is contributed by bhardwajji

Java

import java.util.*;
 
class Main {
    // Function that return Ways to sum to N using
    // Natural Numbers up to K with repetitions allowed
    public static int NumberOfways(int N, int K)
    {
        // Base case
        if (N == 0)
            return 1;
        if (N < 0 || K <= 0)
            return 0;
 
        // including and not including K in sum
        return NumberOfways(N - K, K)
            + NumberOfways(N, K - 1);
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int N = 8;
        int K = 2;
 
        // function call
        System.out.println(NumberOfways(N, K));
    }
}

Python3

# Function that returns the number of ways to sum
# to N using natural numbers up to K with repetitions allowed
 
 
def number_of_ways(N, K):
 
    # Base case
    if N == 0:
        return 1
    if N < 0 or K <= 0:
        return 0
 
    # Including and not including K in sum
    return number_of_ways(N - K, K) + number_of_ways(N, K - 1)
 
 
# Driver code
if __name__ == '__main__':
    N = 8
    K = 2
 
    # Function call
    print(number_of_ways(N, K))

Javascript

// Function that return Ways to sum to N using
// Natural Numbers up to K with repetitions allowed
function numberOfWays(N, K) {
     
    // Base case
    if (N == 0) return 1;
    if (N < 0 || K <= 0) return 0;
     
    // including and not including K in sum
    return numberOfWays(N - K, K) + numberOfWays(N, K - 1);
}
 
 
// Driver code
let N = 8;
let K = 2;
     
// function call
console.log(numberOfWays(N, K));

C#

using System;
 
class MainClass {
    // Function that return Ways to sum to N using
    // Natural Numbers up to K with repetitions allowed
    static int NumberOfWays(int N, int K)
    {
        // Base case
        if (N == 0)
            return 1;
        if (N < 0 || K <= 0)
            return 0;
 
        // including and not including K in sum
        return NumberOfWays(N - K, K)
            + NumberOfWays(N, K - 1);
    }
 
    // Driver code
    static void Main()
    {
        int N = 8;
        int K = 2;
 
        // function call
        Console.WriteLine(NumberOfWays(N, K));
    }
}
// This code is contributed by user_dtewbxkn77n

Output

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

Efficient Approach: The above approach has Overlapping Subproblems and an Optimal Substructure. Hence, in order to optimize, Dynamic Programming is needed to be performed based on the following observations:

Considering dp[i] stores the total number of ways for representing i as the sum of integers lying in the range [1, K], then the transition of states can be defined as:
- For i in the range [1, K] and for every j in the range [1, N]
- The value of dp[j] is equal to (dp[j]+ dp[j – i]), for all j ? i.

Follow the steps below to solve the problem:

Initialize an array, say dp[], with all elements as 0, to store all the recursive states.
Initialize dp[0] as 1.
Now, iterate over the range [1, K] using a variable i and perform the following steps:
- Iterate over the range [1, N], using a variable j, and update the value of dp[j] as dp[j]+ dp[j – i], if j ? i.
After completing the above steps, print the value of dp[N] as the result.

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 total number of
// ways to represent N as the sum of
// integers over the range [1, K]
int NumberOfways(int N, int K)
{
 
    // Initialize a list
    vector<int> dp(N + 1, 0);
   
    // Update dp[0] to 1
    dp[0] = 1;
 
    // Iterate over the range [1, K + 1]
    for (int row = 1; row < K + 1; row++)
    {
 
        // Iterate over the range [1, N + 1]
        for (int col = 1; col < N + 1; col++)
        {
 
            // If col is greater
            // than or equal to row
            if (col >= row)
               
                // Update current
                // dp[col] state
                dp[col] = dp[col] + dp[col - row];
          }
    }
 
    // Return the total number of ways
    return(dp[N]);
}
 
// Driver Code
int main()
{
  int N = 8;
  int K = 2;
 
  cout << (NumberOfways(N, K));
}
 
// This code is contributed by mohit kumar 29.

Java

// Java program for the above approach
import java.util.*;
 
class GFG{
     
// Function to find the total number of
// ways to represent N as the sum of
// integers over the range [1, K]
static int NumberOfways(int N, int K)
{
     
    // Initialize a list
    int[] dp = new int[N + 1];
   
    // Update dp[0] to 1
    dp[0] = 1;
 
    // Iterate over the range [1, K + 1]
    for(int row = 1; row < K + 1; row++)
    {
 
        // Iterate over the range [1, N + 1]
        for(int col = 1; col < N + 1; col++)
        {
             
            // If col is greater
            // than or equal to row
            if (col >= row)
               
                // Update current
                // dp[col] state
                dp[col] = dp[col] + dp[col - row];
          }
    }
 
    // Return the total number of ways
    return(dp[N]);
}
 
// Driver code
public static void main(String[] args)
{
     
    // Given inputs
    int N = 8;
    int K = 2;
     
    System.out.println(NumberOfways(N, K));
}
}
 
// This code is contributed by offbeat

Python

# Python program for the above approach
 
# Function to find the total number of
# ways to represent N as the sum of
# integers over the range [1, K]
def NumberOfways(N, K):
   
    # Initialize a list
    dp = [0] * (N + 1)
     
    # Update dp[0] to 1
    dp[0] = 1
     
    # Iterate over the range [1, K + 1]
    for row in range(1, K + 1):
       
        # Iterate over the range [1, N + 1]
        for col in range(1, N + 1):
           
            # If col is greater
            # than or equal to row
            if (col >= row):
               
                # Update current
                # dp[col] state
                dp[col] = dp[col] + dp[col - row]
                 
                 
    # Return the total number of ways
    return(dp[N])
 
# Driver Code
 
N = 8
K = 2
 
print(NumberOfways(N, K))

Javascript

<script>
// Javascript implementation for the above approach
 
// Function to find the total number of
// ways to represent N as the sum of
// integers over the range [1, K]
function NumberOfways(N, K)
{
     
    // Initialize a list
    let dp = Array.from({length: N +1}, (_, i) => 0);
   
    // Update dp[0] to 1
    dp[0] = 1;
 
    // Iterate over the range [1, K + 1]
    for(let row = 1; row < K + 1; row++)
    {
 
        // Iterate over the range [1, N + 1]
        for(let col = 1; col < N + 1; col++)
        {
             
            // If col is greater
            // than or equal to row
            if (col >= row)
               
                // Update current
                // dp[col] state
                dp[col] = dp[col] + dp[col - row];
          }
    }
 
    // Return the total number of ways
    return(dp[N]);
}
 
    // Driver Code
     
    // Given inputs
    let N = 8;
    let K = 2;
     
    document.write(NumberOfways(N, K));
 
</script>

C#

// C# program for the above approach
using System;
class GFG 
{
   
    // Function to find the total number of
    // ways to represent N as the sum of
    // integers over the range [1, K]
    static int NumberOfways(int N, int K)
    {
 
        // Initialize a list
        int[] dp = new int[(N + 1)];
 
        // Update dp[0] to 1
        dp[0] = 1;
 
        // Iterate over the range [1, K + 1]
        for (int row = 1; row < K + 1; row++) {
 
            // Iterate over the range [1, N + 1]
            for (int col = 1; col < N + 1; col++) {
 
                // If col is greater
                // than or equal to row
                if (col >= row)
 
                    // Update current
                    // dp[col] state
                    dp[col] = dp[col] + dp[col - row];
            }
        }
 
        // Return the total number of ways
        return (dp[N]);
    }
 
    // Driver Code
    public static void Main()
    {
        int N = 8;
        int K = 2;
 
        Console.WriteLine(NumberOfways(N, K));
    }
}
 
// This code is contributed by ukasp.

Output:

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

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 zambiatek!