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 allowedint 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 codeint 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 codeif __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 allowedfunction 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 codelet N = 8;let K = 2;Â Â Â Â Â // function callconsole.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
5
Time Complexity: O(KN)
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 Codeint 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 approachimport 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 codepublic 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 = 8K = 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 approachusing 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:Â
5
Â
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
