Staircase paths avoiding broken steps

Write codeMedium12 min

Your task

A staircase has steps numbered 1 through n, and you start on the ground (position 0). Each move climbs 1 or 2 steps. Some steps are broken and cannot be landed on; their numbers are given in the list broken (all values are between 1 and n, no duplicates). Return the number of distinct ways to reach step n exactly without ever landing on a broken step. If step n itself is broken, return 0.

Examples

count_safe_paths(n: int, broken: list[int]) -> int
Example 1
Inputcount_safe_paths(5, [])
Output8
Example 2
Inputcount_safe_paths(5, [3])
Output2