Given two positive integers N and K, the task is to count the number of ways to write N as a sum of K non-negative integers.
Examples:
Input: N = 2, K = 3
Output: 6
Explanation:
The total ways in which 2 can be split into K non-negative integers are:
1. (0, 0, 2)
2. (0, 2, 0)
3. (2, 0, 0)
4. (0, 1, 1)
5. (1, 0, 1)
6. (1, 1, 0)Input: N = 3, K = 2
Output: 4
Explanation:
The total ways in which can be split 3 into 2 non-negative integers are:
1. (0, 3)
2. (3, 0)
3. (1, 2)
4. (2, 1)
Approach: This problem can be solved using Dynamic Programming. Below are the steps:
- Initialize a 2D array as dp[K+1][N+1] where rows correspond to the number of the element we pick and columns correspond to the corresponding sum.
- Start filling the first row and column with taking sum as K in the above table dp[][].
- Suppose we reach at ith row and jth column, i.e i elements we can pick and we need to get sum j. To calculate the number of ways till dp[i][j] choose first (i – 1) elements and next (j – x) where x is the sum of first (i – 1) elements.
- Repeat the above steps to fill the dp[][] array.
- The value dp[n][m] will give the required 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 count the number of ways// to write N as sum of k non-negative// integersint countWays(int n, int m){ // Initialise dp[][] array int dp[m + 1][n + 1]; // Only 1 way to choose the value // with sum K for (int i = 0; i <= n; i++) { dp[1][i] = 1; } // Initialise sum int sum; for (int i = 2; i <= m; i++) { for (int j = 0; j <= n; j++) { sum = 0; // Count the ways from previous // states for (int k = 0; k <= j; k++) { sum += dp[i - 1][k]; } // Update the sum dp[i][j] = sum; } } // Return the final count of ways return dp[m][n];}// Driver Codeint main(){ int N = 2, K = 3; // Function call cout << countWays(N, K); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to count the number of ways// to write N as sum of k non-negative// integersstatic int countWays(int n, int m){ // Initialise dp[][] array int [][]dp = new int[m + 1][n + 1]; // Only 1 way to choose the value // with sum K for(int i = 0; i <= n; i++) { dp[1][i] = 1; } // Initialise sum int sum; for(int i = 2; i <= m; i++) { for(int j = 0; j <= n; j++) { sum = 0; // Count the ways from previous // states for(int k = 0; k <= j; k++) { sum += dp[i - 1][k]; } // Update the sum dp[i][j] = sum; } } // Return the final count of ways return dp[m][n];}// Driver Codepublic static void main(String[] args){ int N = 2, K = 3; // Function call System.out.print(countWays(N, K));}}// This code is contributed by gauravrajput1 |
Python3
# Python3 program for the above approach# Function to count the number of ways# to write N as sum of k non-negative# integersdef countWays(n, m): # Initialise dp[][] array dp = [[ 0 for i in range(n + 1)] for i in range(m + 1)] # Only 1 way to choose the value # with sum K for i in range(n + 1): dp[1][i] = 1 # Initialise sum sum = 0 for i in range(2, m + 1): for j in range(n + 1): sum = 0 # Count the ways from previous # states for k in range(j + 1): sum += dp[i - 1][k] # Update the sum dp[i][j] = sum # Return the final count of ways return dp[m][n]# Driver Codeif __name__ == '__main__': N = 2 K = 3 # Function call print(countWays(N, K))# This code is contributed by Mohit Kumar |
C#
// C# program for the above approachusing System;class GFG{// Function to count the number of ways// to write N as sum of k non-negative// integersstatic int countWays(int n, int m){ // Initialise [,]dp array int [,]dp = new int[m + 1, n + 1]; // Only 1 way to choose the value // with sum K for(int i = 0; i <= n; i++) { dp[1, i] = 1; } // Initialise sum int sum; for(int i = 2; i <= m; i++) { for(int j = 0; j <= n; j++) { sum = 0; // Count the ways from previous // states for(int k = 0; k <= j; k++) { sum += dp[i - 1, k]; } // Update the sum dp[i, j] = sum; } } // Return the readonly count of ways return dp[m, n];}// Driver Codepublic static void Main(String[] args){ int N = 2, K = 3; // Function call Console.Write(countWays(N, K));}}// This code is contributed by gauravrajput1 |
Javascript
<script>// Javascript program for the above approach// Function to count the number of ways// to write N as sum of k non-negative// integersfunction countWays(n, m){ // Initialise dp[][] array var dp = Array.from(Array(m+1), ()=>Array(n+1)); // Only 1 way to choose the value // with sum K for (var i = 0; i <= n; i++) { dp[1][i] = 1; } // Initialise sum var sum; for (var i = 2; i <= m; i++) { for (var j = 0; j <= n; j++) { sum = 0; // Count the ways from previous // states for (var k = 0; k <= j; k++) { sum += dp[i - 1][k]; } // Update the sum dp[i][j] = sum; } } // Return the final count of ways return dp[m][n];}// Driver Codevar N = 2, K = 3;// Function calldocument.write( countWays(N, K));</script> |
Output:
6
Time Complexity: O(K*N2)
Auxiliary Space Complexity: O(N*K)
Optimized Approach: The idea of calculating the sum and then storing the count increases the time complexity. We can decrease it by storing the sum in the above dp[][] table.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to count the number of ways// to write N as sum of k non-negative// integersint countWays(int n, int m){ // Initialise dp[][] array int dp[m + 1][n + 1]; // Fill the dp[][] with sum = m for (int i = 0; i <= n; i++) { dp[1][i] = 1; if (i != 0) { dp[1][i] += dp[1][i - 1]; } } // Iterate the dp[][] to fill the // dp[][] array for (int i = 2; i <= m; i++) { for (int j = 0; j <= n; j++) { // Condition for first column if (j == 0) { dp[i][j] = dp[i - 1][j]; } // Else fill the dp[][] with // sum till (i, j) else { dp[i][j] = dp[i - 1][j]; // If reach the end, then // return the value if (i == m && j == n) { return dp[i][j]; } // Update at current index dp[i][j] += dp[i][j - 1]; } } }}// Driver Codeint main(){ int N = 2, K = 3; // Function call cout << countWays(N, K); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to count the number of ways// to write N as sum of k non-negative// integersstatic int countWays(int n, int m){ // Initialise dp[][] array int [][]dp = new int[m + 1][n + 1]; // Fill the dp[][] with sum = m for (int i = 0; i <= n; i++) { dp[1][i] = 1; if (i != 0) { dp[1][i] += dp[1][i - 1]; } } // Iterate the dp[][] to fill the // dp[][] array for (int i = 2; i <= m; i++) { for (int j = 0; j <= n; j++) { // Condition for first column if (j == 0) { dp[i][j] = dp[i - 1][j]; } // Else fill the dp[][] with // sum till (i, j) else { dp[i][j] = dp[i - 1][j]; // If reach the end, then // return the value if (i == m && j == n) { return dp[i][j]; } // Update at current index dp[i][j] += dp[i][j - 1]; } } } return Integer.MIN_VALUE;}// Driver Codepublic static void main(String[] args){ int N = 2, K = 3; // Function call System.out.print(countWays(N, K));}}// This code is contributed by sapnasingh4991 |
Python3
# Python3 program for the above approach# Function to count the number of ways# to write N as sum of k non-negative# integersdef countWays(n, m): # Initialise dp[][] array dp = [[0 for i in range(n + 1)] for j in range(m + 1)] # Fill the dp[][] with sum = m for i in range(n + 1): dp[1][i] = 1 if (i != 0): dp[1][i] += dp[1][i - 1] # Iterate the dp[][] to fill the # dp[][] array for i in range(2, m + 1): for j in range(n + 1): # Condition for first column if (j == 0): dp[i][j] = dp[i - 1][j] # Else fill the dp[][] with # sum till (i, j) else: dp[i][j] = dp[i - 1][j] # If reach the end, then # return the value if (i == m and j == n): return dp[i][j] # Update at current index dp[i][j] += dp[i][j - 1] # Driver CodeN = 2K = 3# Function callprint(countWays(N, K))# This code is contributed by ShubhamCoder |
C#
// C# program for the above approachusing System;class GFG{// Function to count the number of ways// to write N as sum of k non-negative// integersstatic int countWays(int n, int m){ // Initialise dp[][] array int [,]dp = new int[m + 1, n + 1]; // Fill the dp[][] with sum = m for (int i = 0; i <= n; i++) { dp[1, i] = 1; if (i != 0) { dp[1, i] += dp[1, i - 1]; } } // Iterate the dp[][] to fill the // dp[][] array for (int i = 2; i <= m; i++) { for (int j = 0; j <= n; j++) { // Condition for first column if (j == 0) { dp[i, j] = dp[i - 1, j]; } // Else fill the dp[][] with // sum till (i, j) else { dp[i, j] = dp[i - 1, j]; // If reach the end, then // return the value if (i == m && j == n) { return dp[i, j]; } // Update at current index dp[i, j] += dp[i, j - 1]; } } } return Int32.MinValue;}// Driver Codepublic static void Main(){ int N = 2, K = 3; // Function call Console.Write(countWays(N, K));}}// This code is contributed by Code_Mech |
Javascript
<script>// JavaScript program for the above approach// Function to count the number of ways// to write N as sum of k non-negative// integersfunction countWays(n,m){ // Initialise dp[][] array let dp = new Array(m + 1); for(let i=0;i<m+1;i++) { dp[i]=new Array(n+1); for(let j=0;j<n+1;j++) dp[i][j]=0; } // Fill the dp[][] with sum = m for (let i = 0; i <= n; i++) { dp[1][i] = 1; if (i != 0) { dp[1][i] += dp[1][i - 1]; } } // Iterate the dp[][] to fill the // dp[][] array for (let i = 2; i <= m; i++) { for (let j = 0; j <= n; j++) { // Condition for first column if (j == 0) { dp[i][j] = dp[i - 1][j]; } // Else fill the dp[][] with // sum till (i, j) else { dp[i][j] = dp[i - 1][j]; // If reach the end, then // return the value if (i == m && j == n) { return dp[i][j]; } // Update at current index dp[i][j] += dp[i][j - 1]; } } } return Number.MIN_VALUE;}// Driver Codelet N = 2, K = 3;// Function calldocument.write(countWays(N, K));// This code is contributed by patel2127</script> |
Output:
6
Time Complexity: O(K*N)
Auxiliary Space: O(N*K)
Efficient Approach : using array instead of 2d matrix to optimize space complexity
In previous code we can se that dp[i][j] is dependent upon dp[i-1][j] or dp[i][j-1] so we can assume that dp[i-1] is previous row and dp[i] is current row.
Implementations Steps :
- Create two vectors prev and curr each of size n+1, where n is a given number.
- Initialize them with base cases.
- Now In previous code change dp[i] to curr and change dp[i-1] to prev to keep track only of the two main rows.
- After every iteration update previous row to current row to iterate further.
Implementation :
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to count the number of ways// to write N as sum of k non-negative// integersint countWays(int n, int m){ // initialize 2 vectors determining 2 rows of DP vector<int>prev(n+1 , 0); vector<int>curr(n+1 , 0); // Base case initialize the prev vector for (int i = 0; i <= n; i++) { prev[i] = 1; if (i != 0) { prev[i] += prev[i - 1]; } } // fill curr vector by the help of prev vector for (int i = 2; i <= m; i++) { for (int j = 0; j <= n; j++) { // Condition for first column if (j == 0) { curr[j] = prev[j]; } // Else fill the curr with // sum till (i, j) else { curr[j] = prev[j]; // If reach the end, then // return the value if (i == m && j == n) { return curr[j]; } // Update at current index curr[j] += curr[j - 1]; } } prev = curr; }}// Driver Codeint main(){ int N = 2, K = 3; // Function call cout << countWays(N, K); return 0;} |
Java
import java.util.*;public class Main { // Function to count the number of ways // to write N as sum of k non-negative // integers static int countWays(int n, int m) { // initialize 2 vectors determining 2 rows of DP int[] prev = new int[n + 1]; int[] curr = new int[n + 1]; // Base case initialize the prev vector for (int i = 0; i <= n; i++) { prev[i] = 1; if (i != 0) { prev[i] += prev[i - 1]; } } // fill curr vector by the help of prev vector for (int i = 2; i <= m; i++) { for (int j = 0; j <= n; j++) { // Condition for first column if (j == 0) { curr[j] = prev[j]; } // Else fill the curr with // sum till (i, j) else { curr[j] = prev[j]; // If reach the end, then // return the value if (i == m && j == n) { return curr[j]; } // Update at current index curr[j] += curr[j - 1]; } } // Update prev array prev = curr.clone(); } return curr[n]; } // Driver Code public static void main(String[] args) { int N = 2, K = 3; // Function call System.out.println(countWays(N, K)); }} |
Python3
# Define a function to count the number of ways to write N as sum of K non-negative integersdef countWays(n, m): # initialize 2 lists determining 2 rows of DP prev = [0] * (n + 1) curr = [0] * (n + 1) # Base case initialize the prev list for i in range(n + 1): prev[i] = 1 if i != 0: prev[i] += prev[i - 1] # fill curr list by the help of prev list for i in range(2, m + 1): for j in range(n + 1): # Condition for first column if j == 0: curr[j] = prev[j] # Else fill the curr with sum till (i, j) else: curr[j] = prev[j] # If reach the end, then return the value if i == m and j == n: return curr[j] # Update at current index curr[j] += curr[j - 1] prev = curr.copy()# Driver CodeN = 2K = 3# Function callprint(countWays(N, K)) |
C#
using System;class GFG{ // Function to count the number of ways // to write N as sum of k non-negative // integers static int countWays(int n, int m) { // Initialize 2 vectors determining 2 rows of DP int[] prev = new int[n + 1]; int[] curr = new int[n + 1]; // Base case initialize the prev vector for (int i = 0; i <= n; i++) { prev[i] = 1; if (i != 0) { prev[i] += prev[i - 1]; } } // Fill curr vector by the help of prev vector for (int i = 2; i <= m; i++) { for (int j = 0; j <= n; j++) { // Condition for first column if (j == 0) { curr[j] = prev[j]; } // Else fill the curr with // sum till (i, j) else { curr[j] = prev[j]; // If reach the end, then // return the value if (i == m && j == n) { return curr[j]; } // Update at current index curr[j] += curr[j - 1]; } } prev = curr; } return curr[n]; } // Driver Code static void Main() { int N = 2, K = 3; // Function call Console.WriteLine(countWays(N, K)); }} |
Javascript
// Function to count the number of ways// to write N as sum of k non-negative// integersfunction countWays(n, m) { // initialize 2 arrays determining 2 rows of DP let prev = new Array(n + 1).fill(0); let curr = new Array(n + 1).fill(0); // Base case initialize the prev array for (let i = 0; i <= n; i++) { prev[i] = 1; if (i != 0) { prev[i] += prev[i - 1]; } } // fill curr array by the help of prev array for (let i = 2; i <= m; i++) { for (let j = 0; j <= n; j++) { // Condition for first column if (j == 0) { curr[j] = prev[j]; } // Else fill the curr with // sum till (i, j) else { curr[j] = prev[j]; // If reach the end, then // return the value if (i == m && j == n) { return curr[j]; } // Update at current index curr[j] += curr[j - 1]; } } prev = [...curr]; }}// Driver Codelet N = 2, K = 3;// Function callconsole.log(countWays(N, K)); |
Output
6
Time Complexity: O(K*N)
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!
