Find number of ways to reach the k th stair

Math Dynamic Programming Bit Manipulation Memoization Combinatorics

37.5% acceptance

Feb 24, 2026

194

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. Operations: - Go down to stair i - 1. This operation cannot be used consecutively or on stair 0. - Go up to stair i + 2^jump. And then, jump becomes jump + 1. Return the total number of ways Alice can reach stair k.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn ways_to_reach_stair(k: i32) -> i32 {
    let k = k as i64;
    // With u ups (using powers 2^0, 2^1, ..., 2^(u-1)) and d downs:
    // final_stair = 1 + (2^u - 1) - d = 2^u - d = k => d = 2^u - k
    // Valid if: 0 <= d <= u+1 (at most 1 down per gap between ups)
    // # of ways = C(u+1, d)
    fn comb(n: i64, r: i64) -> i64 {
      if r < 0 || r > n {
        return 0;
      }
      let r = r.min(n - r);
      let mut result = 1i64;
      for i in 0..r {
        result = result * (n - i) / (i + 1);
      }
      result
    }

    let mut ans = 0i64;
    for u in 0..32i64 {
      let pow2u = 1i64 << u;
      let d = pow2u - k;
      if d < 0 {
        continue;
      }
      if d > u + 1 {
        break;
      }
      ans += comb(u + 1, d);
    }
    ans as i32
  }
}