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

Description

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.

 

Example 1:

Input: k = 0

Output: 2

Explanation:

The 2 possible ways of reaching stair 0 are:

• Alice starts at stair 1.
  • Using an operation of the first type, she goes down 1 stair to reach stair 0.
• Alice starts at stair 1.
  • Using an operation of the first type, she goes down 1 stair to reach stair 0.
  • Using an operation of the second type, she goes up 2⁰ stairs to reach stair 1.
  • Using an operation of the first type, she goes down 1 stair to reach stair 0.

Example 2:

Input: k = 1

Output: 4

Explanation:

The 4 possible ways of reaching stair 1 are:

• Alice starts at stair 1. Alice is at stair 1.
• Alice starts at stair 1.
  • Using an operation of the first type, she goes down 1 stair to reach stair 0.
  • Using an operation of the second type, she goes up 2⁰ stairs to reach stair 1.
• Alice starts at stair 1.
  • Using an operation of the second type, she goes up 2⁰ stairs to reach stair 2.
  • Using an operation of the first type, she goes down 1 stair to reach stair 1.
• Alice starts at stair 1.
  • Using an operation of the first type, she goes down 1 stair to reach stair 0.
  • Using an operation of the second type, she goes up 2⁰ stairs to reach stair 1.
  • Using an operation of the first type, she goes down 1 stair to reach stair 0.
  • Using an operation of the second type, she goes up 2¹ stairs to reach stair 2.
  • Using an operation of the first type, she goes down 1 stair to reach stair 1.

 

Constraints:

• 0 <= k <= 109

 

Solutions

Solution: Dynamic Programming

• Time complexity: O(log²k)
• Space complexity: O(log²k)

 

JavaScript

/**
 * @param {number} k
 * @return {number}
 */
const waysToReachStair = function (k) {
  const memo = new Map();

  const getWaysToReachK = (stairs, jump, prevDown) => {
    if (stairs - 1 > k || stairs < 0) return 0;

    const key = `${stairs},${jump},${Number(prevDown)}`;

    if (memo.has(key)) return memo.get(key);

    let result = stairs === k ? 1 : 0;

    if (!prevDown) {
      result += getWaysToReachK(stairs - 1, jump, true);
    }

    const nextStairs = stairs + 2 ** jump;

    result += getWaysToReachK(nextStairs, jump + 1, false);

    memo.set(key, result);

    return result;
  };

  return getWaysToReachK(1, 0, false);
};