Given a natural number n, find the number of ways in which n can be expressed as a sum of natural numbers when order is taken into consideration. Two sequences that differ in the order of their terms define different compositions of their sum.
Examples:
Input : 4 Output : 8 Explanation All 8 position composition are: 4, 1+3, 3+1, 2+2, 1+1+2, 1+2+1, 2+1+1 and 1+1+1+1 Input : 8 Output : 128
A Simple Solution is to generate all compositions and count them.
Using the concept of combinatorics, it can be proved that any natural number n will have 2^(n-1) distinct compositions when order is taken into consideration.
One way to see why the answer is 2^(n-1) directly is to write n as a sum of 1s:
n = 1 + 1 + 1 +…+ 1 (n times).
There are (n-1) plus signs between all 1s. For every plus sign we can choose to split ( by putting a bracket) at the point or not split. Therefore answer is 2^(n-1).
For example, n = 4
No Split
4 = 1 + 1 + 1 + 1 [We write as single 4]
Different ways to split once
4 = (1) + (1 + 1 + 1) [We write as 1 + 3]
4 = (1 + 1) + (1 + 1) [We write as 2 + 2]
4 = (1 + 1 + 1) + (1) [We write as 3 + 1]
Different ways to split twice
4 = (1) + (1 + 1) + (1) [We write as 1 + 2 + 1]
4 = (1 + 1) + (1) + (1) [We write as 2 + 1 + 1]
4 = (1) + (1) + (1 + 1) [We write as 1 + 1 + 2]
Different ways to split three times
4 = (1) + (1) + (1) + (1) [We write as 1 + 1 + 1 + 1]
Since there are (n-1) plus signs between the n 1s, there are 2^(n-1) ways of choosing where to split the sum, and hence 2^(n-1) possible sums .
C++
// C++ program to find the total number of// compositions of a natural number#include<iostream>using namespace std;#define ull unsigned long longull countCompositions(ull n){ // Return 2 raised to power (n-1) return (1L) << (n-1);}// Driver Codeint main(){ ull n = 4; cout << countCompositions(n) << "\n"; return 0;} |
Java
// Java program to find // the total number of // compositions of a// natural numberimport java.io.*;import java.util.*;class GFG{public static int countCompositions(int n){ // Return 2 raised // to power (n-1) return 1 << (n - 1);}// Driver Codepublic static void main(String args[]){ int n = 4; System.out.print(countCompositions(n));}}// This code is contributed by // Akanksha Rai(Abby_akku) |
Python
# Python code to find the total number of# compositions of a natural numberdef countCompositions(n): # function to return the total number # of composition of n return (2**(n-1))# Driver Codeprint(countCompositions(4)) |
C#
// C# program to find the // total number of compositions// of a natural numberusing System;class GFG{public static int countCompositions(int n){ // Return 2 raised // to power (n-1) return 1 << (n - 1);}// Driver Codepublic static void Main(){ int n = 4; Console.Write(countCompositions(n));}}// This code is contributed by mits |
PHP
<?php// PHP program to find the // total number of compositions // of a natural numberfunction countCompositions($n){ // Return 2 raised // to power (n-1) return ((1) << ($n - 1));}// Driver Code$n = 4;echo countCompositions($n), "\n"; // This code is contributed// by ajit?> |
Javascript
<script>// javascript program to find // the total number of // compositions of a// natural numberfunction countCompositions(n){ // Return 2 raised // to power (n-1) return 1 << (n - 1);}// Driver Code var n = 4; document.write(countCompositions(n));// This code is contributed by 29AjayKumar </script> |
Output:
8
This article is contributed by Sruti Rai . If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Approach#2: Recursion with Memoization
The code uses memoization to efficiently calculate the number of compositions of a given integer using positive integers. The main function, count_compositions_memo, initializes a memo dictionary, and calls the recursive function count_compositions to calculate the result. The count_compositions function uses memoization to avoid redundant calculations, and computes the number of compositions recursively by iterating over all possible values of the first element in the composition and adding up the number of compositions for the remaining sum.
Algorithm
1. Create a dictionary ‘memo’ to store previously computed values.
2. Define a recursive function ‘count_compositions’ which takes n as input.
3. If n == 0, return 1.
4. If n < 0, return 0.
5. If memo[n] is not None, return memo[n].
6. Set memo[n] to 0.
7. Loop from i = 1 to i = n:
a. Add count_compositions(n-i) to memo[n].
8. Return memo[n].
9. Call count_compositions(n) and return its value.
C++
#include <iostream>#include <unordered_map> // include the unordered_map library for memoizationint count_compositions_memo(int n) { std::unordered_map<int, int> memo; // create a memoization table if (n == 0) { return 1; // base case: there is only one way to compose 0 } if (n < 0) { return 0; // base case: there is no way to compose a negative number } if (memo.find(n) != memo.end()) { return memo[n]; // if n is in the memoization table, return its value } int count = 0; for (int i = 1; i <= n; i++) { count += count_compositions_memo(n - i); // recursively count the number of compositions } memo[n] = count; // store the computed value in the memoization table return count;}int main() { int n = 4; std::cout << count_compositions_memo(n) << std::endl; return 0;} |
Python3
def count_compositions_memo(n): memo = {} def count_compositions(n): if n == 0: return 1 if n < 0: return 0 if n in memo: return memo[n] memo[n] = 0 for i in range(1,n+1): memo[n] += count_compositions(n-i) return memo[n] return count_compositions(n)n=4print(count_compositions_memo(n)) |
8
Time complexity: O(n^2)
Auxiliary Space: O(n)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
