Given a number n (number of variables) and val (sum of the variables), find out how many such non-negative integral solutions are possible.
Examples :
Input : n = 5, val = 1
Output : 5
Explanation:
x1 + x2 + x3 + x4 + x5 = 1
Number of possible solution are :
(0 0 0 0 1), (0 0 0 1 0), (0 0 1 0 0),
(0 1 0 0 0), (1 0 0 0 0)
Total number of possible solutions are 5
Input : n = 5, val = 4
Output : 70
Explanation:
x1 + x2 + x3 + x4 + x5 = 4
Number of possible solution are:
(1 1 1 1 0), (1 0 1 1 1), (0 1 1 1 1),
(2 1 0 0 1), (2 2 0 0 0)........ so on......
Total numbers of possible solutions are 70
Asked in: Microsoft Interview
1. Make a recursive function call to countSolutions(int n, int val)
2. Call this Solution function countSolutions(n-1, val-i) until n = 1 and val >=0 and then return 1.
Below is the implementation of above approach:
C++
// CPP program to find the numbers// of non negative integral solutions #include<iostream>using namespace std;// return number of non negative // integral solutionsint countSolutions(int n, int val){ // initialize total = 0 int total = 0; // Base Case if n = 1 and val >= 0 // then it should return 1 if (n == 1 && val >=0) return 1; // iterate the loop till equal the val for (int i = 0; i <= val; i++){ // total solution of equations // and again call the recursive // function Solutions(variable,value) total += countSolutions(n-1, val-i); } // return the total no possible solution return total;}// driver codeint main(){ int n = 5; int val = 20; cout<<countSolutions(n, val);}//This code is contributed by Smitha Dinesh Semwal |
Java
// Java program to find the numbers// of non negative integral solutionsclass GFG { // return number of non negative // integral solutions static int countSolutions(int n, int val) { // initialize total = 0 int total = 0; // Base Case if n = 1 and val >= 0 // then it should return 1 if (n == 1 && val >= 0) return 1; // iterate the loop till equal the val for (int i = 0; i <= val; i++) { // total solution of equations // and again call the recursive // function Solutions(variable, value) total += countSolutions(n - 1, val - i); } // return the total no possible solution return total; } // Driver code public static void main(String[] args) { int n = 5; int val = 20; System.out.print(countSolutions(n, val)); }}// This code is contributed by Anant Agarwal. |
Python3
# Python3 program to find the numbers# of non negative integral solutions # return number of non negative # integral solutionsdef countSolutions(n, val): # initialize total = 0 total = 0 # Base Case if n = 1 and val >= 0 # then it should return 1 if n == 1 and val >=0: return 1 # iterate the loop till equal the val for i in range(val+1): # total solution of equations # and again call the recursive # function Solutions(variable,value) total += countSolutions(n-1, val-i) # return the total no possible solution return total# driver coden = 5val = 20print(countSolutions(n, val)) |
C#
// C# program to find the numbers// of non negative integral solutionsusing System;class GFG { // return number of non negative // integral solutions static int countSolutions(int n, int val) { // initialize total = 0 int total = 0; // Base Case if n = 1 and val >= 0 // then it should return 1 if (n == 1 && val >= 0) return 1; // iterate the loop till equal the val for (int i = 0; i <= val; i++) { // total solution of equations // and again call the recursive // function Solutions(variable, value) total += countSolutions(n - 1, val - i); } // return the total no possible solution return total; } // Driver code public static void Main() { int n = 5; int val = 20; Console.WriteLine(countSolutions(n, val)); }}// This code is contributed by Anant vt_m. |
Javascript
<script>// JavaScript program to find the numbers// of non negative integral solutions // return number of non negative // integral solutions function countSolutions(n, val) { // initialize total = 0 let total = 0; // Base Case if n = 1 and val >= 0 // then it should return 1 if (n == 1 && val >= 0) return 1; // iterate the loop till equal the val for (let i = 0; i <= val; i++) { // total solution of equations // and again call the recursive // function Solutions(variable, value) total += countSolutions(n - 1, val - i); } // return the total no possible solution return total; }// Driver code let n = 5; let val = 20; document.write(countSolutions(n, val)); </script> |
PHP
<?php// PHP program to find the numbers// of non negative integral solutions // return number of non negative // integral solutionsfunction countSolutions($n, $val){ // initialize total = 0 $total = 0; // Base Case if n = 1 and // val >= 0 then it should // return 1 if ($n == 1 && $val >=0) return 1; // iterate the loop // till equal the val for ($i = 0; $i <= $val; $i++) { // total solution of equations // and again call the recursive // function Solutions(variable,value) $total += countSolutions($n - 1, $val - $i); } // return the total // no possible solution return $total;}// Driver Code$n = 5;$val = 20;echo countSolutions($n, $val);// This code is contributed by nitin mittal. ?> |
Output :
10626
Dynamic Programming Approach:
(Using Memoization)
C++
// CPP program to find the numbers// of non negative integral solutions#include<bits/stdc++.h>using namespace std;int dp[1001][1001];// return number of non negative// integral solutionsint countSolutions(int n, int val){ // initialize total = 0 int total = 0; // Base Case if n = 1 and val >= 0 // then it should return 1 if (n == 1 && val >=0) { return 1; } // If a value already present in dp, // return it if(dp[n][val] != -1) { return dp[n][val]; } // iterate the loop till equal the val for (int i = 0; i <= val; i++){ // total solution of equations // and again call the recursive // function Solutions(variable,value) total += countSolutions(n-1, val-i); } // Store the value in dp dp[n][val] = total; // Return dp return dp[n][val];}// driver codeint main(){ int n = 5; int val = 20; memset(dp, -1, sizeof(dp)); cout << countSolutions(n, val);} |
Java
// Java program to find the numbers// of non negative integral solutionsimport java.util.*;public class GFG{ static int dp[][] = new int[1001][1001]; // return number of non negative // integral solutions static int countSolutions(int n, int val) { // initialize total = 0 int total = 0; // Base Case if n = 1 and val >= 0 // then it should return 1 if (n == 1 && val >=0) { return 1; } // If a value already present in dp, // return it if(dp[n][val] != -1) { return dp[n][val]; } // iterate the loop till equal the val for (int i = 0; i <= val; i++){ // total solution of equations // and again call the recursive // function Solutions(variable,value) total += countSolutions(n-1, val-i); } // Store the value in dp dp[n][val] = total; // Return dp return dp[n][val]; } // driver code public static void main(String args[]){ int n = 5; int val = 20; for(int i = 0; i < 1001; i++) { for(int j = 0; j < 1001; j++) { dp[i][j]=-1; } } System.out.println(countSolutions(n, val)); }}// This code is contributed by Samim Hossain Mondal. |
Python3
# Python3 program to find the numbers# of non negative integral solutions # Taking the matrix as globallydp = [[-1 for i in range(1001)] for j in range(1001)]# Return number of non negative # integral solutionsdef countSolutions(n, val): # Initialize total = 0 total = 0 # Base Case if n = 1 and val >= 0 # then it should return 1 if n == 1 and val >= 0: return 1 # If a value is already present # in dp if (dp[n][val] != -1): return dp[n][val] # Iterate the loop till equal the val for i in range(val + 1): # total solution of equations # and again call the recursive # function Solutions(variable,value) total += countSolutions(n - 1, val - i) # Return the total no possible solution dp[n][val] = total return dp[n][val]# Driver coden = 5val = 20print(countSolutions(n, val))# This code is contributed by Samim Hossain Mondal. |
C#
// C# program to find the numbers// of non negative integral solutionsusing System;class GFG{ static int [,]dp = new int[1001, 1001]; // return number of non negative // integral solutions static int countSolutions(int n, int val) { // initialize total = 0 int total = 0; // Base Case if n = 1 and val >= 0 // then it should return 1 if (n == 1 && val >=0) { return 1; } // If a value already present in dp, // return it if(dp[n, val] != -1) { return dp[n, val]; } // iterate the loop till equal the val for (int i = 0; i <= val; i++){ // total solution of equations // and again call the recursive // function Solutions(variable,value) total += countSolutions(n-1, val-i); } // Store the value in dp dp[n, val] = total; // Return dp return dp[n, val]; } // driver code public static void Main(){ int n = 5; int val = 20; for(int i = 0; i < 1001; i++) { for(int j = 0; j < 1001; j++) { dp[i, j] = -1; } } Console.Write(countSolutions(n, val)); }}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script>// JavaScript program to find the numbers// of non negative integral solutions var dp = new Array(1001); // Loop to create 2D array using 1D array for (var i = 0; i < dp.length; i++) { dp[i] = new Array(1001); } // return number of non negative // integral solutions function countSolutions(n, val) { // initialize total = 0 let total = 0; // Base Case if n = 1 and val >= 0 // then it should return 1 if (n == 1 && val >= 0) return 1; // if a value is already // present in dp if(dp[n][val] != -1) return dp[n][val]; // iterate the loop till equal the val for (let i = 0; i <= val; i++) { // total solution of equations // and again call the recursive // function Solutions(variable, value) total += countSolutions(n - 1, val - i); } // return the total no possible solution return dp[n][val] = total; }// Driver codelet n = 5;let val = 20;for(let i = 0; i < 1001; i++) { for(let j = 0; j < 1001; j++) { dp[i][j] = -1; }}document.write(countSolutions(n, val));// This code is contributed by Samim Hossain Mondal. </script> |
Output
10626
Time Complexity: O(n * val)
Auxiliary Space: O(n * val)
Dynamic Programming Approach: (Bottom-Up)
The approach used here is a bottom-up dynamic programming approach. We start with the simplest case (one variable) and build up the solution to the n variables.
- We create a two-dimensional array called dp with dimensions n+1 x val+1, where dp[i][j] represents the number of solutions to the equation with i variables and sum j.
- Since there is only one variable in the first row (i=1), the number of solutions to the equation is always 1. Thus, initialize the first row of dp with all 1’s.
- For each subsequent row (i > 1) and each column j, we calculate dp[i][j] as the sum of dp[i-1][j-k] for all possible values of k between 0 and j. Because, for each solution to the equation with i variables and sum j, we can obtain a solution to the equation with i-1 variables and sum j-k by subtracting k from one of the variables.
- After computing all values of dp[n][j], we return dp[n][val], which represents the number of non-negative integral solutions to the equation with n variables and sum val.
Here is the Java Implementation of above algorithm
C++
#include <iostream>using namespace std;// Function to count the number of // non-negative integral solutionsint Solutions(int n, int val){ int dp[n + 1][val + 1]; // Initialize the first row of the dp array dp[1][j] will have 1 solution for every j for (int i = 0; i <= val; i++) { dp[1][i] = 1; } // Compute the number of solutions for each i and j using previous solutions for (int i = 2; i <= n; i++) { for (int j = 0; j <= val; j++) { dp[i][j] = 0; for (int k = 0; k <= j; k++) { dp[i][j] += dp[i - 1][j - k]; } } } // Return the solution for n variables and sum val return dp[n][val];}// Driver codeint main(){ int n = 5; int val = 20; // Function call cout << Solutions(n, val) << endl; return 0;} |
Java
// Java program to find the numbers// of non negative integral solutions using bottom up// approachimport java.io.*;class GFG { // return number of non negative // integral solutions public static int countSolutions(int n, int val) { // Create a 2D array to store the number of // solutions dp[i][j] will store the number of // solutions for i variables and sum j int dp[][] = new int[n + 1][val + 1]; // Initialize the first row of the dp array // dp[1][j] will have 1 solution for every j for (int i = 0; i <= val; i++) { dp[1][i] = 1; } // Compute the number of solutions for each i and j // using previous solutions for (int i = 2; i <= n; i++) { for (int j = 0; j <= val; j++) { dp[i][j] = 0; // For each k from 0 to j, add the number of // solutions from the previous row // dp[i][j] = dp[i-1][j] + dp[i-1][j-1] + // ... + dp[i-1][j-k] for (int k = 0; k <= j; k++) { dp[i][j] += dp[i - 1][j - k]; } } } // Return the solution for n variables and sum val return dp[n][val]; } // Driver code public static void main(String[] args) { int n = 5; int val = 20; // function call System.out.println(countSolutions(n, val)); }}// This code is contributed by Tapesh(tapeshdua420) |
C#
using System;class GFG{ // Function to return the number of non-negative integral solutions public static int CountSolutions(int n, int val) { // Create a 2D array to store the number of solutions // dp[i][j] will store the number of solutions for i variables and sum j int[,] dp = new int[n + 1, val + 1]; // Initialize the first row of the dp array // dp[1][j] will have 1 solution for every j for (int i = 0; i <= val; i++) { dp[1, i] = 1; } // Compute the number of solutions for each i and j // using previous solutions for (int i = 2; i <= n; i++) { for (int j = 0; j <= val; j++) { dp[i, j] = 0; // For each k from 0 to j, add the number of solutions from the previous row // dp[i][j] = dp[i-1][j] + dp[i-1][j-1] + ... + dp[i-1][j-k] for (int k = 0; k <= j; k++) { dp[i, j] += dp[i - 1, j - k]; } } } // Return the solution for n variables and sum val return dp[n, val]; } // Main method public static void Main(string[] args) { int n = 5; int val = 20; // Function call Console.WriteLine(CountSolutions(n, val)); }} |
Javascript
// JavaScript program to find the numbers// of non negative integral solutions using bottom up// approach// return number of non negative// integral solutionsfunction countSolutions(n, val) { // Create a 2D array to store the number of // solutions dp[i][j] will store the number of // solutions for i variables and sum j const dp = new Array(n + 1).fill(null).map(() => new Array(val + 1).fill(0)); // Initialize the first row of the dp array // dp[1][j] will have 1 solution for every j for (let i = 0; i <= val; i++) { dp[1][i] = 1; } // Compute the number of solutions for each i and j // using previous solutions for (let i = 2; i <= n; i++) { for (let j = 0; j <= val; j++) { dp[i][j] = 0; // For each k from 0 to j, add the number of // solutions from the previous row // dp[i][j] = dp[i-1][j] + dp[i-1][j-1] + // ... + dp[i-1][j-k] for (let k = 0; k <= j; k++) { dp[i][j] += dp[i - 1][j - k]; } } } // Return the solution for n variables and sum val return dp[n][val];}// Driver codeconst n = 5;const val = 20;// function callconsole.log(countSolutions(n, val)); |
Output
10626
Complexity Analysis
Time Complexity : O(n * val^2), where n is the number of variables and val is the given sum.
Auxiliary Space : O( n * val), creating a 2D array of size (n + 1) * (val + 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!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
