Number of Ways to Sum 1, 3 and 4
MediumP3Coding
Count the ways to write n as a sum of 1s, 3s and 4s where the order of the terms matters. For example, n = 5 has 6 ways: 1+1+1+1+1, 1+1+3, 1+3+1, 3+1+1, 1+4 and 4+1.
By convention there is one way (the empty sum) to write 0.
Example 1
- Input
- n = 5
- Output
- 6
- Why
- Six ordered sums.
Example 2
- Input
- n = 1
- Output
- 1
Example 3
- Input
- n = 0
- Output
- 1
Constraints
- 0 <= n <= 70
- The answer fits in a 53-bit integer.
Hints
Give it a real attempt first. Run shows which examples fail.
Saved automatically
Run checks the 3 visible tests, Submit all 11. ⌘Enter runs, ⌘⇧Enter submits.