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 alloweddef 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 CodeN = 8K = 2print(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!
