A cashier wants to split N identical coins into one or more stacks. Each stack must hold at least one coin, and the stacks are unlabeled, so only the multiset of stack sizes matters (for example, splitting 4 coins as 3+1 is the same as 1+3).
Count the number of distinct ways to split N coins into stacks. If N is 0, there is exactly one way: no stacks at all.
A single line: the integer N.
A single integer: the number of distinct partitions of N.
Example 1
Input
4
Expected
5
Explanation
The partitions of 4 are 4, 3+1, 2+2, 2+1+1, and 1+1+1+1, so the answer is 5.
Example 2
Input
1
Expected
1
Explanation
The only partition of 1 is a single stack of one coin, so the answer is 1.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →