The Step Counter

An easy Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

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.

You can hop one step or two - how many ways to 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
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.

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.
The direct transcription
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.

Common follow-up questions