Tap here to switch tabs
Problem
Submissions

Problem: Find Number of Ways to Reach the K-th Stair

Find Number of Ways to Reach the K-th Stair asks you to count distinct operation sequences that take Alice from stair 1 to stair k, with growing upward jumps and no consecutive downward moves.

Statement

You are given a non negative integer k. There is an infinite staircase with stairs numbered from 00 to infinity. Alice starts on stair 11 and has a variable jump initialized to 00.

Alice can perform two types of operations:

  1. Move down to stair i−1i - 1, where ii is her current stair. This operation cannot be performed consecutively or when Alice is already at stair 00.

  2. Move up to stair i+2jumpi + 2^{ {jump}}. Afterwards, increment jump by 11.

Return the total number of distinct ways Alice can reach stair k.

Note: A way is defined by the sequence of operations performed to reach stair k. Reaching stair k multiple times across different points in an execution path counts as a distinct way at each arrival.

Constraints:

  • 0≤0 \leq k ≤109\leq 10^9

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Find Number of Ways to Reach the K-th Stair

Find Number of Ways to Reach the K-th Stair asks you to count distinct operation sequences that take Alice from stair 1 to stair k, with growing upward jumps and no consecutive downward moves.

Statement

You are given a non negative integer k. There is an infinite staircase with stairs numbered from 00 to infinity. Alice starts on stair 11 and has a variable jump initialized to 00.

Alice can perform two types of operations:

  1. Move down to stair i−1i - 1, where ii is her current stair. This operation cannot be performed consecutively or when Alice is already at stair 00.

  2. Move up to stair i+2jumpi + 2^{ {jump}}. Afterwards, increment jump by 11.

Return the total number of distinct ways Alice can reach stair k.

Note: A way is defined by the sequence of operations performed to reach stair k. Reaching stair k multiple times across different points in an execution path counts as a distinct way at each arrival.

Constraints:

  • 0≤0 \leq k ≤109\leq 10^9