Ways to Reach N with Steps 4 and 8
MediumP3Coding
Starting from 0, you repeatedly add either 4 or 8 until you land exactly on n. Count the number of different sequences of additions that reach n; the order of the additions matters (4 then 8 differs from 8 then 4). Reaching n = 0 takes no additions and counts as 1 way.
If n cannot be reached, return 0.
Example 1
- Input
- n = 12
- Output
- 3
- Why
- 4+4+4, 4+8 and 8+4.
Example 2
- Input
- n = 4
- Output
- 1
- Why
- A single step of 4.
Example 3
- Input
- n = 8
- Output
- 2
Constraints
- 0 <= n <= 300
- 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 12. ⌘Enter runs, ⌘⇧Enter submits.