Number Factors
Medium · Dynamic Programming · Math · Dynamic Programming · Memoization
Problem
Given a positive integer n, count the different ways to write n as an ordered sum of the numbers 1, 3 and 4.
Order matters: 1 + 3 and 3 + 1 are two different ways. Every part must be exactly 1, 3 or 4, and a part may be used any number of times.
Return the count. It fits in a 64-bit signed integer for the given limits.
Examples
Input: n = 4 Output: 4
The four ways are 4, 1+3, 3+1 and 1+1+1+1.
Input: n = 5 Output: 6
The ways are 1+4, 4+1, 1+1+3, 1+3+1, 3+1+1 and 1+1+1+1+1.
Input: n = 2 Output: 1
Only 1+1 works, because 3 and 4 are larger than 2.
Constraints
- 1 <= n <= 60
Approaches
- Recursion on what is left, with a memo — time O(n), space O(n)
Follow-up
The same table counts ordered sums for any set of parts: add one term per part. The use cases fix the number of parts (which also opens a counting-by-formula route) and forbid two equal parts in a row, which makes the last part part of the state.
Related problems
Start free on Cariara · Coding problems · System design studio
