Loading…

mediumDynamic ProgrammingFrequently asked

Davis' Staircase

Q: How do you solve Davis' Staircase using the Brute Force — Plain Triple Recursion (Exponential) approach?

When to use it: State it to derive and justify the recurrence, then flag the exponential 3-way branching to motivate memoisation. Translate the recurrence directly. `ways(n)` asks for the number of ordered jump sequences summing to `n`. Condition on the final jump: - If it was a **1-step** jump, the preceding climb reached `n-1` → `ways(n-1)` possibilities. - If it was a **2-step** jump, the preceding climb reached `n-2` → `ways(n-2)`. - If it was a **3-step** jump, the preceding climb reached `n-3` → `ways(n-3)`. These cases partition all climbs (every climb has exactly one last jump), so `ways(n) = ways(n-1) + ways(n-2) + ways(n-3)`. **Base cases.** `ways(0) = 1`: there is exactly one way to have climbed nothing. For negatives we return 0 — a jump that overshoots the bottom isn't a valid climb. With these, `ways(1)=1`, `ways(2)=ways(1)+ways(0)=2`, `ways(3)=ways(2)+ways(1)+ways(0)=4`, matching the hand count. **Why it's too slow.** Without caching, `ways(n-3)` is recomputed in the `n-1`, `n-2`, and `n-3` subtrees, exploding to ~3^n calls. The fix is to remember each `ways(k)` the first time it's computed. Time complexity: O(3^n). Space complexity: O(n) recursion stack.

Q: How do you solve Davis' Staircase using the Bottom-Up Tribonacci DP (Optimal) approach?

When to use it: The answer they want. Phrase it as 'fill ways[0..n] left to right with the tribonacci recurrence mod 10¹⁰+7'. Memoising the recursion in the natural order gives a clean table. Allocate `ways[0..n]`, seed the three base cases, then fill forward. **The fill.** For each `i ≥ 3`, the three predecessors `ways[i-1]`, `ways[i-2]`, `ways[i-3]` are already final, so `ways[i] = (ways[i-1] + ways[i-2] + ways[i-3]) % MOD` is computed once and never revisited. **Why modulo at every step.** We take the remainder as we go, not just at the end, so the running values never exceed `MOD`. Each summand is `< 10¹⁰`; three of them sum to `< 3×10¹⁰`, which exceeds the 32-bit `int` ceiling (~2.1×10⁹) but sits comfortably inside signed 64-bit `long` (~9.2×10¹⁸). So accumulate in `long`, reduce after the addition. **Why it's correct and minimal.** It's the same recurrence as the brute force, just evaluated in dependency order with each result stored. No recomputation, no recursion depth — linear time, trivially fast for n ≤ 36 and fine well beyond. Time complexity: O(n). Space complexity: O(n).

Q: How do you solve Davis' Staircase using the Rolling Variables — O(1) Space approach?

When to use it: Mention as the memory-tight refinement: only the last three values are ever needed. The full array is unnecessary because the recurrence has a fixed window of three. Hold the last three counts in `a`, `b`, `c` (oldest to newest). Each step computes `next = (a + b + c) % MOD`, then slides the window: `a = b`, `b = c`, `c = next`. **Why it matches the table.** It evaluates exactly the same sequence of sums in the same order; only storage shrinks from `n+1` cells to three scalars. After the loop reaches `i = n`, `c` holds `ways(n)`. **When to use it.** Whenever n could be large and memory matters, or simply to show you recognise the bounded dependency window. For n ≤ 36 either form is instant, but the rolling version is the cleaner production answer. Time complexity: O(n). Space complexity: O(1).

Dynamic Programming · 44 of 44 · 9 min

Davis has a number of staircases, and he can climb exactly 1, 2, or 3 steps at a time. Given the number of steps n in a staircase, count the total number of distinct ways Davis can climb to the top.

Because the count grows quickly, return the answer modulo 10000000007 (that is, 10¹⁰ + 7).

In plain English

We count ordered sequences of jumps of size 1, 2, or 3 that sum to n. The crucial reframing: classify every full climb by its final jump. If the last jump was 1 step, the rest is a climb of n-1; if 2 steps, a climb of n-2; if 3 steps, a climb of n-3. These three cases are disjoint and exhaustive, so the total is their sum. The empty climb (n=0) counts as exactly one way — that base case is what gives the correct totals for small n.

Examples

Example 1

Input: n = 1
Output: 1
Note: Only one way: a single 1-step jump.

Example 2

Input: n = 3
Output: 4
Note: {1,1,1}, {1,2}, {2,1}, {3} — four ordered climbs. Equals ways(2)+ways(1)+ways(0) = 2+1+1 = 4.

Example 3

Input: n = 5
Output: 13
Note: ways(5) = ways(4)+ways(3)+ways(2) = 7+4+2 = 13.

Example 4

Input: n = 7
Output: 44
Note: ways(6)=24, ways(5)=13, ways(4)=7 → ways(7) = 24+13+7 = 44.

Constraints

1 ≤ s ≤ 100 (number of independent staircases / queries)
1 ≤ n ≤ 36 (steps per staircase, per HackerRank)
Davis may ascend by exactly 1, 2, or 3 steps in a single move
Answer must be returned modulo 10000000007 (10¹⁰ + 7)

Clarifying questions4First question: Does the order of jumps matter — is (1 then 2) different from (2 then 1)?Explore questions

Q1.Does the order of jumps matter — is (1 then 2) different from (2 then 1)?
Yes. Davis taking 1-then-2 is a distinct climb from 2-then-1. That's why this is tribonacci (ordered) and not a coin-change combination count.
Q2.What does ways(0) represent and why is it 1?
It's the empty climb — standing at the bottom with nothing to do. Defining it as 1 makes ways(3) include the single jump of 3 (3 = arrive from step 0), giving the correct ways(3) = 4.
Q3.Which modulus exactly — 10⁹+7 or 10¹⁰+7?
10000000007, i.e. 10¹⁰ + 7. HackerRank uses the larger modulus here; reflexively typing 1000000007 (10⁹+7) is wrong.
Q4.Can n be large enough to need matrix exponentiation?
Not at n ≤ 36 — linear DP is instant. But if n were up to 10¹⁸, the 3×3 transition matrix raised to the n-th power gives O(log n).

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Davis can climb 1, 2, or 3 steps at a time; count the distinct ways to reach the top of an n-step staircase. The number of ways to land on step n is the sum of the ways to land on the three steps you could have jumped from: ways(n) = ways(n-1) + ways(n-2) + ways(n-3). This is the tribonacci recurrence with ways(0)=1, ways(1)=1, ways(2)=2. Compute it bottom-up in O(n) time, O(1) space, taking everything modulo 10000000007 as HackerRank requires.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you decompose the count by the last move into a clean recurrence, identify it as tribonacci, seed the base cases correctly, and avoid exponential recursion.

Where candidates slip

Forgetting ways(0)=1, miscounting base cases so ways(3) comes out as 3 instead of 4, using the wrong modulus (10⁹+7), or recursing without memoisation.

How to stand out

Derive the recurrence from 'what was my last jump?', state the three base cases with justification, give O(n)/O(1) DP, and mention O(log n) matrix exponentiation for huge n.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Plain Triple Recursion (Exponential)	`O(3^n)`	`O(n) recursion stack`	State it to derive and justify the recurrence, then flag the exponential 3-way branching to motivate memoisation.	Read
2	Bottom-Up Tribonacci DP (Optimal)Optimal	`O(n)`	`O(n)`	The answer they want. Phrase it as 'fill ways[0..n] left to right with the tribonacci recurrence mod 10¹⁰+7'.	Read
3	Rolling Variables — O(1) Space	`O(n)`	`O(1)`	Mention as the memory-tight refinement: only the last three values are ever needed.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.Explore the full tree

Decompose by the last jump

How to read it:Every climb to n ends with a jump of 1, 2, or 3 — sum the ways to reach each landing spot.

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 3

Brute Force — Plain Triple Recursion (Exponential)

TimeO(3^n)SpaceO(n) recursion stack

State it to derive and justify the recurrence, then flag the exponential 3-way branching to motivate memoisation.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Ask: what was the very last jump? It was 1, 2, or 3 steps, so it landed from step n-1, n-2, or n-3.

2Hint 2Explore hint

The total ways to reach n is the sum of the ways to reach those three earlier steps — recurse on each.

3Hint 3Explore hint

Base cases: reaching step 0 counts as 1 (empty climb); negative steps count as 0 (illegal jump).

A · Core idea

Translate the recurrence directly. ways(n) asks for the number of ordered jump sequences summing to n. Condition on the final jump:

If it was a 1-step jump, the preceding climb reached n-1 → ways(n-1) possibilities.
If it was a 2-step jump, the preceding climb reached n-2 → ways(n-2).
If it was a 3-step jump, the preceding climb reached n-3 → ways(n-3).

These cases partition all climbs (every climb has exactly one last jump), so ways(n) = ways(n-1) + ways(n-2) + ways(n-3).

Base cases. ways(0) = 1: there is exactly one way to have climbed nothing. For negatives we return 0 — a jump that overshoots the bottom isn't a valid climb. With these, ways(1)=1, ways(2)=ways(1)+ways(0)=2, ways(3)=ways(2)+ways(1)+ways(0)=4, matching the hand count.

Why it's too slow. Without caching, ways(n-3) is recomputed in the n-1, n-2, and n-3 subtrees, exploding to ~3^n calls. The fix is to remember each ways(k) the first time it's computed.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 3

Interactive diagram

Triple-branching recursion tree

ways(3)

Active call / nodeSupporting contextReturned stateNot active

ways(1) and ways(0) are reached by several paths — the redundancy DP removes.

Final result4

C · Code with teaching comments

Reference implementation previewstatic final long MOD = 10000000007L; public long stepPerms(int n) { if (n < 0) return 0; if (n == 0) return 1;Explore the full code

solution.javaJava

Brute Force — Plain Triple Recursion (Exponential) — reference

3 teaching notes

1
static final long MOD = 10000000007L;
2
 
3
public long stepPerms(int n) {
4
    // A jump that overshoots the bottom is not a valid climb.
5
    if (n < 0) return 0;
6
    // The empty climb counts once — this seed makes the small cases correct.
7
    if (n == 0) return 1;
8
    // Sum the three last-jump cases; reduce mod 10¹⁰+7.
9
    return (stepPerms(n - 1) + stepPerms(n - 2) + stepPerms(n - 3)) % MOD;
10
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.10 lines

D · Why it works and complexityO(3^n) timeO(n) recursion stack spaceOpen the invariant and proofExplore the proof

The 'condition on the last move' trick is the workhorse of counting DPs. Once you see the three disjoint cases, the recurrence writes itself — and the fact that ways(n-3) reappears across branches is the precise signal to memoise.

ComplexityO(3^n) time, O(n) recursion stack space — Each call spawns up to three recursive calls and the depth is ~n, so the tree has up to 3^n nodes. The same subproblem (e.g. ways(n-3)) is recomputed along many branches.

E · Edge cases and pitfalls3Forgetting the n==0 → 1 base case, which throws off every larger value.Explore edge cases

Pitfalls

Forgetting the n==0 → 1 base case, which throws off every larger value.
Not handling negative n, causing array/index errors or wrong counts.
Running this unmemoised — 3^n is hopeless even for moderate n.

03.2

Approach 2 of 3 · Optimal

Bottom-Up Tribonacci DP (Optimal)

TimeO(n)SpaceO(n)

The answer they want. Phrase it as 'fill ways[0..n] left to right with the tribonacci recurrence mod 10¹⁰+7'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Build an array ways[0..n]. Seed ways[0]=1, ways[1]=1, ways[2]=2.

2Hint 2Explore hint

For i from 3 to n: ways[i] = (ways[i-1] + ways[i-2] + ways[i-3]) % 10000000007.

3Hint 3Explore hint

Return ways[n]. Every value is computed exactly once, so it's linear.

A · Core idea

Memoising the recursion in the natural order gives a clean table. Allocate ways[0..n], seed the three base cases, then fill forward.

The fill. For each i ≥ 3, the three predecessors ways[i-1], ways[i-2], ways[i-3] are already final, so ways[i] = (ways[i-1] + ways[i-2] + ways[i-3]) % MOD is computed once and never revisited.

Why modulo at every step. We take the remainder as we go, not just at the end, so the running values never exceed MOD. Each summand is < 10¹⁰; three of them sum to < 3×10¹⁰, which exceeds the 32-bit int ceiling (~2.1×10⁹) but sits comfortably inside signed 64-bit long (~9.2×10¹⁸). So accumulate in long, reduce after the addition.

Why it's correct and minimal. It's the same recurrence as the brute force, just evaluated in dependency order with each result stored. No recomputation, no recursion depth — linear time, trivially fast for n ≤ 36 and fine well beyond.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 5

Array state

seed

ways[0..2] = 1,1,2

[0]

[1]

[2]

Current pointerResolved stateNot processed

Final result13

C · Code with teaching comments

solution.javaJava

Bottom-Up Tribonacci DP (Optimal) — optimal

3 teaching notes

1
static final long MOD = 10000000007L;
2
 
3
public long stepPerms(int n) {
4
    if (n == 0) return 1;
5
    if (n == 1) return 1;
6
    if (n == 2) return 2;
7
    long[] ways = new long[n + 1];
8
    // The three tribonacci seeds; ways[0]=1 is the empty climb.
9
    ways[0] = 1; ways[1] = 1; ways[2] = 2;
10
    for (int i = 3; i <= n; i++) {
11
        // Sum the three predecessors and reduce mod 10000000007.
12
        ways[i] = (ways[i - 1] + ways[i - 2] + ways[i - 3]) % MOD;
13
    }
14
    // Last entry is the count for n steps.
15
    return ways[n];
16
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.16 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

Filling the table in increasing index order means every dependency is already final when you need it — that's the whole reason bottom-up DP avoids both recursion overhead and recomputation. Apply the modulus inside the loop so intermediate sums stay bounded.

ComplexityO(n) time, O(n) space — One pass from 3 to n, O(1) work per index → O(n) time. The array of size n+1 → O(n) space (reducible to O(1)).

E · Edge cases and pitfalls6n = 1 — Returns the seed 1 directly.Explore edge cases

Edge cases handled

n = 1Returns the seed 1 directly.
n = 2Returns 2 — {1,1} and {2}.
n = 3First loop iteration: 2+1+1 = 4.

Pitfalls

Using 1000000007 (10⁹+7) instead of 10000000007 — silent wrong answer.
Accumulating in int — three residues near 10¹⁰ overflow 32 bits; use long.
Off-by-one seeds, e.g. setting ways[2]=1 instead of 2, which corrupts everything after.

03.3

Approach 3 of 3

Rolling Variables — O(1) Space

TimeO(n)SpaceO(1)

Mention as the memory-tight refinement: only the last three values are ever needed.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

ways[i] depends only on the previous three values — you never look further back.

2Hint 2Explore hint

Keep three scalars a=ways(i-3), b=ways(i-2), c=ways(i-1); compute the next, then shift.

3Hint 3Explore hint

Initialise a,b,c to ways(0),ways(1),ways(2) = 1,1,2 and iterate from i=3 to n.

A · Core idea

The full array is unnecessary because the recurrence has a fixed window of three. Hold the last three counts in a, b, c (oldest to newest). Each step computes next = (a + b + c) % MOD, then slides the window: a = b, b = c, c = next.

Why it matches the table. It evaluates exactly the same sequence of sums in the same order; only storage shrinks from n+1 cells to three scalars. After the loop reaches i = n, c holds ways(n).

When to use it. Whenever n could be large and memory matters, or simply to show you recognise the bounded dependency window. For n ≤ 36 either form is instant, but the rolling version is the cleaner production answer.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 4

Array state

init

a=1, b=1, c=2

[0]

[1]

[2]

Current pointerResolved stateNot processed

Final result7

C · Code with teaching comments

Reference implementation previewstatic final long MOD = 10000000007L; public long stepPerms(int n) { if (n == 0 || n == 1) return 1; if (n == 2) return 2;Explore the full code

solution.javaJava

Rolling Variables — O(1) Space — reference

4 teaching notes

1
static final long MOD = 10000000007L;
2
 
3
public long stepPerms(int n) {
4
    if (n == 0 || n == 1) return 1;
5
    if (n == 2) return 2;
6
    // Window holds the three most recent counts.
7
    long a = 1, b = 1, c = 2;  // ways(0), ways(1), ways(2)
8
    for (int i = 3; i <= n; i++) {
9
        // Tribonacci step on the current window.
10
        long next = (a + b + c) % MOD;
11
        // Slide the window forward by one.
12
        a = b; b = c; c = next;
13
    }
14
    // After reaching i=n, c holds ways(n).
15
    return c;
16
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.16 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

A linear recurrence with a fixed-width window never needs more memory than that window. Three rolling scalars replace the whole array — the same trick that turns Fibonacci's array into two variables.

ComplexityO(n) time, O(1) space — Same n iterations, but only three variables held at once → O(1) space.

E · Edge cases and pitfalls6n = 1 — Returns 1 before the loop runs.Explore edge cases

Edge cases handled

n = 1Returns 1 before the loop runs.
n = 2Returns the seed 2.
n = 3One iteration: next = 1+1+2 = 4 → c = 4.

Pitfalls

Shifting the variables in the wrong order, corrupting the window — compute next first.
Returning b or a instead of c after the loop.
Skipping the mod inside the loop and only applying it at the end — fine in Python, but in Java the long can stay clean either way; keep it inside for consistency.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewstatic final long MOD = 10000000007L; public long stepPerms(int n) { if (n == 0) return 1; if (n == 1) return 1;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Wrong modulus

The reflexive competitive-programming modulus is 10⁹+7, but Davis' Staircase specifies 10¹⁰+7. Using the smaller one fails large-n tests even though small cases pass.

Explore the code comparison

Don't write this

static final long MOD = 1000000007L;   // 10^9 + 7 — WRONG here

Write this instead

static final long MOD = 10000000007L;  // 10^10 + 7 — HackerRank's modulus

Missing the ways(0)=1 base case

Without the empty-climb seed, a single jump of 3 (arriving from step 0) isn't counted, so ways(3) comes out 3 instead of 4 and the error propagates upward.

Explore the code comparison

Don't write this

if n == 1: return 1
if n == 2: return 2
if n == 3: return 3   # wrong: forgot the {3} climb

Write this instead

ways[0], ways[1], ways[2] = 1, 1, 2  # ways(0)=1 makes ways(3)=4

Int overflow on the sum

Three residues just under 10¹⁰ sum to nearly 3×10¹⁰, overflowing 32-bit int (max ~2.1×10⁹). The reduced value then looks plausible but is corrupt.

Explore the code comparison

Don't write this

int next = (a + b + c) % MOD;  // int overflow before the mod

Write this instead

long next = (a + b + c) % MOD;  // accumulate in 64-bit

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Tribonacci DP — count-the-ways via last-move decomposition

Code pattern to memorize

ways(0) = 1   # one way to stand at the bottom (do nothing)
ways(1) = 1
ways(2) = 2
ways(n) = (ways(n-1) + ways(n-2) + ways(n-3)) mod 10000000007

Rules to remember

1The recurrence sums the last move's options: the final jump was 1, 2, or 3 steps, landing from n-1, n-2, or n-3.
2Seed exactly three base cases: ways(0)=1, ways(1)=1, ways(2)=2. Getting ways(0)=1 (the empty climb) is what makes ways(3)=4 come out right.
3HackerRank's modulus is 10000000007 (10¹⁰ + 7), NOT the usual 10⁹+7. Hard-coding 1e9+7 is a silent wrong-answer.
4The sum of three residues each < 10¹⁰ is < 3×10¹⁰, which overflows 32-bit int but fits in 64-bit long — use long.
5Plain recursion without memoisation is exponential (each call branches three ways); memoise or go bottom-up.

Use this pattern when

Counting ordered ways to reach a target where each step adds a fixed set of move sizes
Staircase / tiling / coin-ordering problems where order matters
Last-step decomposition cleanly splits the count into a sum of subproblems
You see '1, 2, or 3 at a time' or any small fixed move set

Choose another pattern when

Order does NOT matter (combinations, not permutations) → coin-change-style DP, different recurrence
Move sizes are arbitrary / part of the input → generalise to ways(n) = Σ ways(n - move)
n is astronomically large (10¹⁸) → matrix exponentiation for O(log n)
You must enumerate the actual sequences, not count them → backtracking, not DP

Interview takeaway

Count-the-ways problems decompose by the last action: sum the counts of every state you could have arrived from. For 1/2/3 steps that's the tribonacci recurrence — the direct cousin of Climbing Stairs (1/2 steps → Fibonacci).

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternCount-the-ways via last-move decomposition: ways(n) = Σ ways(n − move). With moves {1,2,3} it's the tribonacci recurrence; with {1,2} it's Fibonacci (Climbing Stairs). Seed the empty-climb base case ways(0)=1, mind the exact modulus, and accumulate in 64-bit.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Climbing Stairs
Only 1 or 2 steps allowed → the Fibonacci version of this exact recurrence.
N-th Tribonacci Number
Coming soon
The bare tribonacci sequence — same recurrence, different seeds.
Combination Sum IV
Coming soon
Generalises the move set to an arbitrary array; same 'sum over last move' DP.
Davis' Staircase for huge n
Raise the 3×3 tribonacci transition matrix to the n-th power for O(log n).

Same pattern

←

Password Cracker

mediumDynamic ProgrammingFrequently asked

Davis' Staircase

Dynamic Programming · 44 of 44 · 9 min

Because the count grows quickly, return the answer modulo 10000000007 (that is, 10¹⁰ + 7).

In plain English

Examples

Example 1

Input: n = 1
Output: 1
Note: Only one way: a single 1-step jump.

Example 2

Input: n = 3
Output: 4
Note: {1,1,1}, {1,2}, {2,1}, {3} — four ordered climbs. Equals ways(2)+ways(1)+ways(0) = 2+1+1 = 4.

Example 3

Input: n = 5
Output: 13
Note: ways(5) = ways(4)+ways(3)+ways(2) = 7+4+2 = 13.

Example 4

Input: n = 7
Output: 44
Note: ways(6)=24, ways(5)=13, ways(4)=7 → ways(7) = 24+13+7 = 44.

Constraints

1 ≤ s ≤ 100 (number of independent staircases / queries)
1 ≤ n ≤ 36 (steps per staircase, per HackerRank)
Davis may ascend by exactly 1, 2, or 3 steps in a single move
Answer must be returned modulo 10000000007 (10¹⁰ + 7)

Clarifying questions4First question: Does the order of jumps matter — is (1 then 2) different from (2 then 1)?Explore questions

Q1.Does the order of jumps matter — is (1 then 2) different from (2 then 1)?
Yes. Davis taking 1-then-2 is a distinct climb from 2-then-1. That's why this is tribonacci (ordered) and not a coin-change combination count.
Q2.What does ways(0) represent and why is it 1?
It's the empty climb — standing at the bottom with nothing to do. Defining it as 1 makes ways(3) include the single jump of 3 (3 = arrive from step 0), giving the correct ways(3) = 4.
Q3.Which modulus exactly — 10⁹+7 or 10¹⁰+7?
10000000007, i.e. 10¹⁰ + 7. HackerRank uses the larger modulus here; reflexively typing 1000000007 (10⁹+7) is wrong.
Q4.Can n be large enough to need matrix exponentiation?
Not at n ≤ 36 — linear DP is instant. But if n were up to 10¹⁸, the 3×3 transition matrix raised to the n-th power gives O(log n).

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you decompose the count by the last move into a clean recurrence, identify it as tribonacci, seed the base cases correctly, and avoid exponential recursion.

Where candidates slip

Forgetting ways(0)=1, miscounting base cases so ways(3) comes out as 3 instead of 4, using the wrong modulus (10⁹+7), or recursing without memoisation.

How to stand out

Derive the recurrence from 'what was my last jump?', state the three base cases with justification, give O(n)/O(1) DP, and mention O(log n) matrix exponentiation for huge n.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Plain Triple Recursion (Exponential)	`O(3^n)`	`O(n) recursion stack`	State it to derive and justify the recurrence, then flag the exponential 3-way branching to motivate memoisation.	Read
2	Bottom-Up Tribonacci DP (Optimal)Optimal	`O(n)`	`O(n)`	The answer they want. Phrase it as 'fill ways[0..n] left to right with the tribonacci recurrence mod 10¹⁰+7'.	Read
3	Rolling Variables — O(1) Space	`O(n)`	`O(1)`	Mention as the memory-tight refinement: only the last three values are ever needed.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.Explore the full tree

Decompose by the last jump

How to read it:Every climb to n ends with a jump of 1, 2, or 3 — sum the ways to reach each landing spot.

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 3

Brute Force — Plain Triple Recursion (Exponential)

TimeO(3^n)SpaceO(n) recursion stack

State it to derive and justify the recurrence, then flag the exponential 3-way branching to motivate memoisation.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Ask: what was the very last jump? It was 1, 2, or 3 steps, so it landed from step n-1, n-2, or n-3.

2Hint 2Explore hint

The total ways to reach n is the sum of the ways to reach those three earlier steps — recurse on each.

3Hint 3Explore hint

Base cases: reaching step 0 counts as 1 (empty climb); negative steps count as 0 (illegal jump).

A · Core idea

Translate the recurrence directly. ways(n) asks for the number of ordered jump sequences summing to n. Condition on the final jump:

If it was a 1-step jump, the preceding climb reached n-1 → ways(n-1) possibilities.
If it was a 2-step jump, the preceding climb reached n-2 → ways(n-2).
If it was a 3-step jump, the preceding climb reached n-3 → ways(n-3).

These cases partition all climbs (every climb has exactly one last jump), so ways(n) = ways(n-1) + ways(n-2) + ways(n-3).

Why it's too slow. Without caching, ways(n-3) is recomputed in the n-1, n-2, and n-3 subtrees, exploding to ~3^n calls. The fix is to remember each ways(k) the first time it's computed.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 3

Interactive diagram

Triple-branching recursion tree

ways(3)

Active call / nodeSupporting contextReturned stateNot active

ways(1) and ways(0) are reached by several paths — the redundancy DP removes.

Final result4

C · Code with teaching comments

Reference implementation previewstatic final long MOD = 10000000007L; public long stepPerms(int n) { if (n < 0) return 0; if (n == 0) return 1;Explore the full code

solution.javaJava

Brute Force — Plain Triple Recursion (Exponential) — reference

3 teaching notes

1
static final long MOD = 10000000007L;
2
 
3
public long stepPerms(int n) {
4
    // A jump that overshoots the bottom is not a valid climb.
5
    if (n < 0) return 0;
6
    // The empty climb counts once — this seed makes the small cases correct.
7
    if (n == 0) return 1;
8
    // Sum the three last-jump cases; reduce mod 10¹⁰+7.
9
    return (stepPerms(n - 1) + stepPerms(n - 2) + stepPerms(n - 3)) % MOD;
10
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.10 lines

D · Why it works and complexityO(3^n) timeO(n) recursion stack spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls3Forgetting the n==0 → 1 base case, which throws off every larger value.Explore edge cases

Pitfalls

Forgetting the n==0 → 1 base case, which throws off every larger value.
Not handling negative n, causing array/index errors or wrong counts.
Running this unmemoised — 3^n is hopeless even for moderate n.

03.2

Approach 2 of 3 · Optimal

Bottom-Up Tribonacci DP (Optimal)

TimeO(n)SpaceO(n)

The answer they want. Phrase it as 'fill ways[0..n] left to right with the tribonacci recurrence mod 10¹⁰+7'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Build an array ways[0..n]. Seed ways[0]=1, ways[1]=1, ways[2]=2.

2Hint 2Explore hint

For i from 3 to n: ways[i] = (ways[i-1] + ways[i-2] + ways[i-3]) % 10000000007.

3Hint 3Explore hint

Return ways[n]. Every value is computed exactly once, so it's linear.

A · Core idea

Memoising the recursion in the natural order gives a clean table. Allocate ways[0..n], seed the three base cases, then fill forward.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 5

Array state

seed

ways[0..2] = 1,1,2

[0]

[1]

[2]

Current pointerResolved stateNot processed

Final result13

C · Code with teaching comments

solution.javaJava

Bottom-Up Tribonacci DP (Optimal) — optimal

3 teaching notes

1
static final long MOD = 10000000007L;
2
 
3
public long stepPerms(int n) {
4
    if (n == 0) return 1;
5
    if (n == 1) return 1;
6
    if (n == 2) return 2;
7
    long[] ways = new long[n + 1];
8
    // The three tribonacci seeds; ways[0]=1 is the empty climb.
9
    ways[0] = 1; ways[1] = 1; ways[2] = 2;
10
    for (int i = 3; i <= n; i++) {
11
        // Sum the three predecessors and reduce mod 10000000007.
12
        ways[i] = (ways[i - 1] + ways[i - 2] + ways[i - 3]) % MOD;
13
    }
14
    // Last entry is the count for n steps.
15
    return ways[n];
16
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.16 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

ComplexityO(n) time, O(n) space — One pass from 3 to n, O(1) work per index → O(n) time. The array of size n+1 → O(n) space (reducible to O(1)).

E · Edge cases and pitfalls6n = 1 — Returns the seed 1 directly.Explore edge cases

Edge cases handled

n = 1Returns the seed 1 directly.
n = 2Returns 2 — {1,1} and {2}.
n = 3First loop iteration: 2+1+1 = 4.

Pitfalls

Using 1000000007 (10⁹+7) instead of 10000000007 — silent wrong answer.
Accumulating in int — three residues near 10¹⁰ overflow 32 bits; use long.
Off-by-one seeds, e.g. setting ways[2]=1 instead of 2, which corrupts everything after.

03.3

Approach 3 of 3

Rolling Variables — O(1) Space

TimeO(n)SpaceO(1)

Mention as the memory-tight refinement: only the last three values are ever needed.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

ways[i] depends only on the previous three values — you never look further back.

2Hint 2Explore hint

Keep three scalars a=ways(i-3), b=ways(i-2), c=ways(i-1); compute the next, then shift.

3Hint 3Explore hint

Initialise a,b,c to ways(0),ways(1),ways(2) = 1,1,2 and iterate from i=3 to n.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 4

Array state

init

a=1, b=1, c=2

[0]

[1]

[2]

Current pointerResolved stateNot processed

Final result7

C · Code with teaching comments

Reference implementation previewstatic final long MOD = 10000000007L; public long stepPerms(int n) { if (n == 0 || n == 1) return 1; if (n == 2) return 2;Explore the full code

solution.javaJava

Rolling Variables — O(1) Space — reference

4 teaching notes

1
static final long MOD = 10000000007L;
2
 
3
public long stepPerms(int n) {
4
    if (n == 0 || n == 1) return 1;
5
    if (n == 2) return 2;
6
    // Window holds the three most recent counts.
7
    long a = 1, b = 1, c = 2;  // ways(0), ways(1), ways(2)
8
    for (int i = 3; i <= n; i++) {
9
        // Tribonacci step on the current window.
10
        long next = (a + b + c) % MOD;
11
        // Slide the window forward by one.
12
        a = b; b = c; c = next;
13
    }
14
    // After reaching i=n, c holds ways(n).
15
    return c;
16
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.16 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

ComplexityO(n) time, O(1) space — Same n iterations, but only three variables held at once → O(1) space.

E · Edge cases and pitfalls6n = 1 — Returns 1 before the loop runs.Explore edge cases

Edge cases handled

n = 1Returns 1 before the loop runs.
n = 2Returns the seed 2.
n = 3One iteration: next = 1+1+2 = 4 → c = 4.

Pitfalls

Shifting the variables in the wrong order, corrupting the window — compute next first.
Returning b or a instead of c after the loop.
Skipping the mod inside the loop and only applying it at the end — fine in Python, but in Java the long can stay clean either way; keep it inside for consistency.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewstatic final long MOD = 10000000007L; public long stepPerms(int n) { if (n == 0) return 1; if (n == 1) return 1;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Wrong modulus

The reflexive competitive-programming modulus is 10⁹+7, but Davis' Staircase specifies 10¹⁰+7. Using the smaller one fails large-n tests even though small cases pass.

Explore the code comparison

Don't write this

static final long MOD = 1000000007L;   // 10^9 + 7 — WRONG here

Write this instead

static final long MOD = 10000000007L;  // 10^10 + 7 — HackerRank's modulus

Missing the ways(0)=1 base case

Without the empty-climb seed, a single jump of 3 (arriving from step 0) isn't counted, so ways(3) comes out 3 instead of 4 and the error propagates upward.

Explore the code comparison

Don't write this

if n == 1: return 1
if n == 2: return 2
if n == 3: return 3   # wrong: forgot the {3} climb

Write this instead

ways[0], ways[1], ways[2] = 1, 1, 2  # ways(0)=1 makes ways(3)=4

Int overflow on the sum

Three residues just under 10¹⁰ sum to nearly 3×10¹⁰, overflowing 32-bit int (max ~2.1×10⁹). The reduced value then looks plausible but is corrupt.

Explore the code comparison

Don't write this

int next = (a + b + c) % MOD;  // int overflow before the mod

Write this instead

long next = (a + b + c) % MOD;  // accumulate in 64-bit

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Tribonacci DP — count-the-ways via last-move decomposition

Code pattern to memorize

ways(0) = 1   # one way to stand at the bottom (do nothing)
ways(1) = 1
ways(2) = 2
ways(n) = (ways(n-1) + ways(n-2) + ways(n-3)) mod 10000000007

Rules to remember

1The recurrence sums the last move's options: the final jump was 1, 2, or 3 steps, landing from n-1, n-2, or n-3.
2Seed exactly three base cases: ways(0)=1, ways(1)=1, ways(2)=2. Getting ways(0)=1 (the empty climb) is what makes ways(3)=4 come out right.
3HackerRank's modulus is 10000000007 (10¹⁰ + 7), NOT the usual 10⁹+7. Hard-coding 1e9+7 is a silent wrong-answer.
4The sum of three residues each < 10¹⁰ is < 3×10¹⁰, which overflows 32-bit int but fits in 64-bit long — use long.
5Plain recursion without memoisation is exponential (each call branches three ways); memoise or go bottom-up.

Use this pattern when

Counting ordered ways to reach a target where each step adds a fixed set of move sizes
Staircase / tiling / coin-ordering problems where order matters
Last-step decomposition cleanly splits the count into a sum of subproblems
You see '1, 2, or 3 at a time' or any small fixed move set

Choose another pattern when

Order does NOT matter (combinations, not permutations) → coin-change-style DP, different recurrence
Move sizes are arbitrary / part of the input → generalise to ways(n) = Σ ways(n - move)
n is astronomically large (10¹⁸) → matrix exponentiation for O(log n)
You must enumerate the actual sequences, not count them → backtracking, not DP

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Climbing Stairs
Only 1 or 2 steps allowed → the Fibonacci version of this exact recurrence.
N-th Tribonacci Number
Coming soon
The bare tribonacci sequence — same recurrence, different seeds.
Combination Sum IV
Coming soon
Generalises the move set to an arbitrary array; same 'sum over last move' DP.
Davis' Staircase for huge n
Raise the 3×3 tribonacci transition matrix to the n-th power for O(log n).

Same pattern

←

Password Cracker