Ways to write n as sum of two or more positive integers
For a given number n > 0, find the number of different ways in which n can be written as a sum of two or more positive integers.
Examples:
Input : n = 5 Output : 6 Explanation : All possible six ways are : 4 + 1 3 + 2 3 + 1 + 1 2 + 2 + 1 2 + 1 + 1 + 1 1 + 1 + 1 + 1 + 1 Input : 4 Output : 4 Explanation : All possible four ways are : 3 + 1 2 + 2 2 + 1 + 1 1 + 1 + 1 + 1
This problem can be solved in a similar fashion as coin change problem, the difference is only that in this case we should iterate for 1 to n-1 instead of particular values of coin as in coin-change problem.
C++
// Program to find the number of ways, n can be // written as sum of two or more positive integers. #include <bits/stdc++.h> using namespace std; // Returns number of ways to write n as sum of // two or more positive integers int countWays( int n) { // table[i] will be storing the number of // solutions for value i. We need n+1 rows // as the table is constructed in bottom up // manner using the base case (n = 0) int table[n+1]; // Initialize all table values as 0 memset (table, 0, sizeof (table)); // Base case (If given value is 0) table[0] = 1; // Pick all integer one by one and update the // table[] values after the index greater // than or equal to n for ( int i=1; i<n; i++) for ( int j=i; j<=n; j++) table[j] += table[j-i]; return table[n]; } // Driver program int main() { int n = 7; cout << countWays(n); return 0; } |
Java
// Program to find the number of ways, // n can be written as sum of two or // more positive integers. import java.util.Arrays; class GFG { // Returns number of ways to write // n as sum of two or more positive // integers static int countWays( int n) { // table[i] will be storing the // number of solutions for value // i. We need n+1 rows as the // table is constructed in bottom // up manner using the base case // (n = 0) int table[] = new int [n + 1 ]; // Initialize all table values as 0 Arrays.fill(table, 0 ); // Base case (If given value is 0) table[ 0 ] = 1 ; // Pick all integer one by one and // update the table[] values after // the index greater than or equal // to n for ( int i = 1 ; i < n; i++) for ( int j = i; j <= n; j++) table[j] += table[j - i]; return table[n]; } //driver code public static void main (String[] args) { int n = 7 ; System.out.print(countWays(n)); } } // This code is contributed by Anant Agarwal. |
Python3
# Program to find the number of ways, n can be # written as sum of two or more positive integers. # Returns number of ways to write n as sum of # two or more positive integers def CountWays(n): # table[i] will be storing the number of # solutions for value i. We need n+1 rows # as the table is constructed in bottom up # manner using the base case (n = 0) # Initialize all table values as 0 table = [ 0 ] * (n + 1 ) # Base case (If given value is 0) # Only 1 way to get 0 (select no integer) table[ 0 ] = 1 # Pick all integer one by one and update the # table[] values after the index greater # than or equal to n for i in range ( 1 , n ): for j in range (i , n + 1 ): table[j] + = table[j - i] return table[n] # driver program def main(): n = 7 print (CountWays(n)) if __name__ = = '__main__' : main() #This code is contributed by Neelam Yadav |
C#
// Program to find the number of ways, n can be // written as sum of two or more positive integers. using System; class GFG { // Returns number of ways to write n as sum of // two or more positive integers static int countWays( int n) { // table[i] will be storing the number of // solutions for value i. We need n+1 rows // as the table is constructed in bottom up // manner using the base case (n = 0) int []table = new int [n+1]; // Initialize all table values as 0 for ( int i = 0; i < table.Length; i++) table[i] = 0; // Base case (If given value is 0) table[0] = 1; // Pick all integer one by one and update the // table[] values after the index greater // than or equal to n for ( int i = 1; i < n; i++) for ( int j = i; j <= n; j++) table[j] += table[j-i]; return table[n]; } //driver code public static void Main() { int n = 7; Console.Write(countWays(n)); } } // This code is contributed by Anant Agarwal. |
PHP
<?php // Program to find the number of ways, n can be // written as sum of two or more positive integers. // Returns number of ways to write n as sum // of two or more positive integers function countWays( $n ) { // table[i] will be storing the number of // solutions for value i. We need n+1 rows // as the table is constructed in bottom up // manner using the base case (n = 0) $table = array_fill (0, $n + 1, NULL); // Base case (If given value is 0) $table [0] = 1; // Pick all integer one by one and update // the table[] values after the index // greater than or equal to n for ( $i = 1; $i < $n ; $i ++) for ( $j = $i ; $j <= $n ; $j ++) $table [ $j ] += $table [ $j - $i ]; return $table [ $n ]; } // Driver Code $n = 7; echo countWays( $n ); // This code is contributed by ita_c ?> |
Javascript
<script> function countWays(n) { // table[i] will be storing the // number of solutions for value // i. We need n+1 rows as the // table is constructed in bottom // up manner using the base case // (n = 0) let table = new Array(n + 1); // Initialize all table values as 0 for (let i = 0; i < n + 1; i++) { table[i]=0; } // Base case (If given value is 0) table[0] = 1; // Pick all integer one by one and // update the table[] values after // the index greater than or equal // to n for (let i = 1; i < n; i++) for (let j = i; j <= n; j++) table[j] += table[j - i]; return table[n]; } let n = 7; document.write(countWays(n)); // This code is contributed by avanitrachhadiya2155 </script> |
Output
14
Time Complexity: O(n2)
Auxiliary Space: O(n)
Contact Us