Skip to content

3154. Find Number of Ways to Reach the K-th Stair 👍

  • Time: $O(\texttt{kMaxJump}^2) = O(1)$
  • Space: $O(\texttt{kMaxJump}) = O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
 public:
  int waysToReachStair(int k) {
    // Let's say we have `down` operation 1 and `jump` operation 2.
    // The final stair is 1 + (2^0 + 2^1 + ... + 2^(jump - 1)) - down = k.
    // => 1 + (2^jump - 1) - down = k.
    // => down = 2^jump - k.
    // Since `down` operations cannot be used consecutively, there're jump + 1
    // positions (before and after each `jump`) for  `down`. The maximum jump is
    // 29, as it satisfies the condition down = 2^jump - k <= jump + 1, with k
    // being the maximum value of 10^9.
    constexpr int kMaxJump = 29;
    const vector<vector<int>> comb = getComb(kMaxJump + 1, kMaxJump + 1);
    int ans = 0;

    for (int jump = 0; jump <= kMaxJump; ++jump) {
      const int down = (1 << jump) - k;
      if (down < 0 || down > jump + 1)
        continue;
      ans += comb[jump + 1][down];
    }

    return ans;
  }

 private:
  // C(n, k) = C(n - 1, k) + C(n - 1, k - 1)
  vector<vector<int>> getComb(int n, int k) {
    vector<vector<int>> comb(n + 1, vector<int>(k + 1));
    for (int i = 0; i <= n; ++i)
      comb[i][0] = 1;
    for (int i = 1; i <= n; ++i)
      for (int j = 1; j <= k; ++j)
        comb[i][j] = comb[i - 1][j] + comb[i - 1][j - 1];
    return comb;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
  public int waysToReachStair(int k) {
    // Let's say we have `down` operation 1 and `jump` operation 2.
    // The final stair is 1 + (2^0 + 2^1 + ... + 2^(jump - 1)) - down = k.
    // => 1 + (2^jump - 1) - down = k.
    // => down = 2^jump - k.
    // Since `down` operations cannot be used consecutively, there're jump + 1
    // positions (before and after each `jump`) for  `down`. The maximum jump is
    // 29, as it satisfies the condition down = 2^jump - k <= jump + 1, with k
    // being the maximum value of 10^9.
    final int kMaxJump = 29;
    final int[][] comb = getComb(kMaxJump + 1, kMaxJump + 1);
    int ans = 0;

    for (int jump = 0; jump <= kMaxJump; ++jump) {
      final int down = (1 << jump) - k;
      if (down < 0 || down > jump + 1)
        continue;
      ans += comb[jump + 1][down];
    }

    return ans;
  }

  // C(n, k) = C(n - 1, k) + C(n - 1, k - 1)
  private int[][] getComb(int n, int k) {
    int[][] comb = new int[n + 1][k + 1];

    for (int i = 0; i <= n; ++i)
      comb[i][0] = 1;
    for (int i = 1; i <= n; ++i)
      for (int j = 1; j <= k; ++j)
        comb[i][j] = comb[i - 1][j] + comb[i - 1][j - 1];
    return comb;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
  def waysToReachStair(self, k: int) -> int:
    # Let's say we have `down` operation 1 and `jump` operation 2.
    # The final stair is 1 + (2^0 + 2^1 + ... + 2^(jump - 1)) - down = k.
    # => 1 + (2^jump - 1) - down = k.
    # => down = 2^jump - k.
    # Since `down` operations cannot be used consecutively, there're jump + 1
    # positions (before and after each `jump`) for  `down`. The maximum jump is
    # 29, as it satisfies the condition down = 2^jump - k <= jump + 1, with k
    # being the maximum value of 10^9.
    kMaxJump = 29
    ans = 0

    for jump in range(kMaxJump + 1):
      down = (1 << jump) - k
      if down < 0 or down > jump + 1:
        continue
      ans += math.comb(jump + 1, down)

    return ans