C++ Programming Code Examples

C++ > Sorting Searching Code Examples

Find the Number of Ways to Write a Number as the Sum of Numbers Smaller than Itself



Find the Number of Ways to Write a Number as the Sum of Numbers Smaller than Itself

- This algorithm counts the partition of the given number.
- There is no straight method to count a total number of the partition so we need to generate and count them.
- The time complexity of this algorithm is O(n!).

- This algorithm takes the input of a number 'n'.
- It starts with the number and breaks it by removing 1, at a time..
- As it generates a new partition increase the counter.
- Print the result.
- Exit.

#include<iostream>
 
using namespace std;
 
// A function to count all the possible partition.
int CountPartitions(int n)
{
    int p[n], k = 0, count = -1;
	p[k] = n;
 
    // Loop until all the array elements converted to 1 mean no further partition can be generated.
    while(1)
    {
        count++;
        int rem_val = 0;
 
        // Move the pointer to the index so that p[k] > 1.
        while (k >= 0 && p[k] == 1)
        {
            rem_val += p[k];
			k--;
        }
        // If k < 0 then the all the element are broken down to 1.
        if (k < 0)  
            return count;
 
        // If value greater than 1 is found then decrease it by 1 and increase rem_val to add it to other elements.
        p[k]--;
        rem_val++;
 
        // Loop until the number of 1's are greater than the value at k index.
        while (rem_val > p[k])
        {
            p[k+1] = p[k];
            // Decrease the rem_val value.
            rem_val = rem_val - p[k];
            k++;
        }
 
        // Assign the remaining value to the index next to k.
        p[k+1] = rem_val;
        k++;
    }
}
 
int main()
{
    int n, c;
    cout<<"Enter natural numbers for partition counting: ";
	cin>>n;
	if (n <= 0)
	{
		cout<<"Wrong input!!";
		return 0;
	}
 
	c = CountPartitions(n);
	cout<<"The number of partitions of with each element lesser than "<<n<<" is:- "<<c;
 
    return 0;
}