# The Step Counter > You can hop one step or two - how many ways to reach the top? Canonical URL: Domain: Python · Difficulty: easy · Seniority: L3 ## Problem We count 1-then-2 and 2-then-1 as different climbs, because the order of the moves is the climb. For a staircase of `n` steps where each move covers 1 or 2 of them, return how many different climbs reach the top. ## Example 1 Input: ``` n = 4 ``` Output: ``` 5 ``` ## Example 2 Input: ``` n = 0 ``` Output: ``` 1 ``` ## Worked solution and explanation ### What this really is Underneath the staircase, this is an ordered-sequence count: how many strings of 1s and 2s add up to `n`. Nearly everyone reaches for a recurrence or a formula within a minute, so the method is not what gets graded. Two things separate candidates. The first is respecting order, since 1-then-2 and 2-then-1 are different climbs. The second is **where the count starts**: the empty staircase is one climb (no moves, already at the top), and textbook seeds of 0 and 1 land every answer one term early. Get the anchor wrong and `n` = 10 comes back 55 instead of 89, while the small cases you checked by hand still look fine. #### Step 1: Look at the last move Every climb to step `n` ends with either a 1-step from `n - 1` or a 2-step from `n - 2`. Those two groups never overlap and together cover everything, so the count at `n` is the count at `n - 1` plus the count at `n - 2`. Because order matters, 1-then-2 and 2-then-1 land in different groups, which is exactly why each one is counted. #### Step 2: Pin the bottom of the staircase Zero steps is one climb and one step is one climb. Those two answers do not come out of the recurrence; they are the ground it stands on. The guard `if n <= 1: return 1` states this directly and returns before any accumulation starts. #### Step 3: Seed from the first real case Start the two rolling counts at step 1 (one climb) and step 2 (two climbs), then walk from step 3 up to `n`. Each pass shifts the window up one step with a single tuple assignment, so the old value is never overwritten before it is used. **Two rolling counts, guarded base** ```python def count_paths(n: int) -> int: if n <= 1: return 1 ways_two_back = 1 ways_one_back = 2 for _ in range(3, n + 1): ways_two_back, ways_one_back = ways_one_back, ways_one_back + ways_two_back return ways_one_back ``` *The loop never runs for `n` = 2, so the seeds themselves are the answer there.* > **The guard owns the bottom two steps** > > The seeds start at step 2, so the function does not still work if you delete the guard: `count_paths(0)` and `count_paths(1)` would both return 2. The early return is the only thing that tells the function an empty staircase is a single climb. **Textbook Fibonacci seeds** Start at 0 and 1 and you compute `F(n)`: 5 steps gives 5, 10 steps gives 55. Every answer is one term short. **Staircase seeds** Anchor at one climb for 0 and 1 steps and two climbs for 2 steps, and you compute `F(n + 1)`: 4 steps gives 5, 10 steps gives 89. > **Arranging the moves is the same count** > > You can also fix how many 2-steps a climb uses, say `k`, and count the ways to place them among `n - k` moves. Summing those arrangements gives the same 5 for 4 steps and the same 1 for an empty staircase. It is the same ordered counting from another angle. The answer that breaks is the one that counts only how many 1s and 2s a climb uses, which gives 3 for 4 steps. **The direct transcription** ```python def count_paths(n: int) -> int: if n == 1: return 1 if n == 2: return 2 return count_paths(n - 1) + count_paths(n - 2) ``` *Recurses past zero for `n` = 0 and repeats the same subproblems exponentially.* > **Base cases at 1 and 2 leave zero falling through** > > The transcription above handles 1 and 2. For an empty staircase it calls itself on -1 and -2 and never stops. Candidates who test only 2 and 3 never see it. > **Linear time, two integers of memory** > > The naive recursion makes roughly `F(n)` calls: past a million at 30 steps, over a billion at 45. The rolling version does `n - 2` additions and holds two numbers regardless of `n`. > **Say why zero steps is one climb** > > Strong candidates justify the base case before coding it: the empty sequence of moves is a valid climb. Writing `return 1` without the reason reads as memorized; explaining it reads as understood. ## Common follow-up questions - What if a move could also cover 3 steps? _(The window grows to three rolling counts and the guard must cover one more base step.)_ - What if `n` reaches 10^6 and the answer must be reported modulo 10^9 + 7? _(Tests reducing inside the loop so the integers stay small.)_ - What if some steps are broken and cannot be landed on? _(A broken step contributes zero climbs, so its count resets before the window moves on.)_ ## Related - [All practice problems](https://datadriven.io/problems) - [Mock interview mode](https://datadriven.io/interview/the_step_counter) - [Python Interview Questions](https://datadriven.io/python-interview-questions) - [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep) - [Daily Challenge](https://datadriven.io/daily) --- Source: DataDriven (https://datadriven.io). DataDriven is the data engineering interview community. Live code execution in SQL, Python, and Spark sandboxes. Every feature is open to every member.