Overflow in intermediate arithmetic
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.
Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.
You are given a non-negative integer k. There exists a staircase with an infinite number of stairs, with the lowest stair numbered 0.
Alice has an integer jump, with an initial value of 0. She starts on stair 1 and wants to reach stair k using any number of operations. If she is on stair i, in one operation she can:
i - 1. This operation cannot be used consecutively or on stair 0.i + 2jump. And then, jump becomes jump + 1.Return the total number of ways Alice can reach stair k.
Note that it is possible that Alice reaches the stair k, and performs some operations to reach the stair k again.
Example 1:
Input: k = 0
Output: 2
Explanation:
The 2 possible ways of reaching stair 0 are:
Example 2:
Input: k = 1
Output: 4
Explanation:
The 4 possible ways of reaching stair 1 are:
Constraints:
0 <= k <= 109Problem summary: You are given a non-negative integer k. There exists a staircase with an infinite number of stairs, with the lowest stair numbered 0. Alice has an integer jump, with an initial value of 0. She starts on stair 1 and wants to reach stair k using any number of operations. If she is on stair i, in one operation she can: Go down to stair i - 1. This operation cannot be used consecutively or on stair 0. Go up to stair i + 2jump. And then, jump becomes jump + 1. Return the total number of ways Alice can reach stair k. Note that it is possible that Alice reaches the stair k, and performs some operations to reach the stair k again.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Math · Dynamic Programming · Bit Manipulation
0
1
climbing-stairs)min-cost-climbing-stairs)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #3154: Find Number of Ways to Reach the K-th Stair
class Solution {
private Map<Long, Integer> f = new HashMap<>();
private int k;
public int waysToReachStair(int k) {
this.k = k;
return dfs(1, 0, 0);
}
private int dfs(int i, int j, int jump) {
if (i > k + 1) {
return 0;
}
long key = ((long) i << 32) | jump << 1 | j;
if (f.containsKey(key)) {
return f.get(key);
}
int ans = i == k ? 1 : 0;
if (i > 0 && j == 0) {
ans += dfs(i - 1, 1, jump);
}
ans += dfs(i + (1 << jump), 0, jump + 1);
f.put(key, ans);
return ans;
}
}
// Accepted solution for LeetCode #3154: Find Number of Ways to Reach the K-th Stair
func waysToReachStair(k int) int {
f := map[int]int{}
var dfs func(i, j, jump int) int
dfs = func(i, j, jump int) int {
if i > k+1 {
return 0
}
key := (i << 32) | jump<<1 | j
if v, has := f[key]; has {
return v
}
ans := 0
if i == k {
ans++
}
if i > 0 && j == 0 {
ans += dfs(i-1, 1, jump)
}
ans += dfs(i+(1<<jump), 0, jump+1)
f[key] = ans
return ans
}
return dfs(1, 0, 0)
}
# Accepted solution for LeetCode #3154: Find Number of Ways to Reach the K-th Stair
class Solution:
def waysToReachStair(self, k: int) -> int:
@cache
def dfs(i: int, j: int, jump: int) -> int:
if i > k + 1:
return 0
ans = int(i == k)
if i > 0 and j == 0:
ans += dfs(i - 1, 1, jump)
ans += dfs(i + (1 << jump), 0, jump + 1)
return ans
return dfs(1, 0, 0)
// Accepted solution for LeetCode #3154: Find Number of Ways to Reach the K-th Stair
/**
* [3154] Find Number of Ways to Reach the K-th Stair
*/
pub struct Solution {}
// submission codes start here
impl Solution {
pub fn ways_to_reach_stair(k: i32) -> i32 {
let mut n = 0;
let mut pos = 1;
let mut result = 0;
loop {
if pos - n - 1 <= k && k <= pos {
result += Self::combine(n + 1, pos - k);
}
if pos - n - 1 > k {
break;
}
n += 1;
pos *= 2;
}
result
}
/// C_n^k = \frac{n * (n - 1) * .. * (n - k + 1)}{1 * 2 * 3 * ... * k}
fn combine(n: i32, k: i32) -> i32 {
let mut result: i64 = 1;
let (n, k) = (n as i64, k as i64);
for i in (n - k + 1..=n).rev() {
result *= i;
result /= n - i + 1;
}
result as i32
}
}
// submission codes end
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_3154() {
assert_eq!(2, Solution::ways_to_reach_stair(0));
assert_eq!(4, Solution::ways_to_reach_stair(1));
}
}
// Accepted solution for LeetCode #3154: Find Number of Ways to Reach the K-th Stair
function waysToReachStair(k: number): number {
const f: Map<bigint, number> = new Map();
const dfs = (i: number, j: number, jump: number): number => {
if (i > k + 1) {
return 0;
}
const key: bigint = (BigInt(i) << BigInt(32)) | BigInt(jump << 1) | BigInt(j);
if (f.has(key)) {
return f.get(key)!;
}
let ans: number = 0;
if (i === k) {
ans++;
}
if (i > 0 && j === 0) {
ans += dfs(i - 1, 1, jump);
}
ans += dfs(i + (1 << jump), 0, jump + 1);
f.set(key, ans);
return ans;
};
return dfs(1, 0, 0);
}
Use this to step through a reusable interview workflow for this problem.
Pure recursion explores every possible choice at each step. With two choices per state (take or skip), the decision tree has 2ⁿ leaves. The recursion stack uses O(n) space. Many subproblems are recomputed exponentially many times.
Each cell in the DP table is computed exactly once from previously solved subproblems. The table dimensions determine both time and space. Look for the state variables — each unique combination of state values is one cell. Often a rolling array can reduce space by one dimension.
Review these before coding to avoid predictable interview regressions.
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.
Wrong move: An incomplete state merges distinct subproblems and caches incorrect answers.
Usually fails on: Correctness breaks on cases that differ only in hidden state.
Fix: Define state so each unique subproblem maps to one DP cell.