Count Ways to Climb n Stairs Using One-Step and Two-Step Moves
Company: Goldman Sachs
Role: Quantitative Researcher
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You stand at the bottom of a staircase with `n` steps. Each move climbs either one step or two steps. Count the number of distinct ways to reach the top, that is, to land exactly on step `n`.
### Function Signature
```python
def count_climb_ways(n: int) -> int:
```
`n` is the number of steps in the staircase.
### Rules
- A way is an ordered sequence of moves, each of size 1 or 2, whose sizes add up to exactly `n`.
- Sequences that use the same moves in a different order are different ways: climbing 1 then 2 differs from climbing 2 then 1.
- You may not climb past step `n`.
### Constraints
- `1 <= n <= 70`
- The answer exceeds `2^31 - 1` once `n >= 46`, but stays below `2^53` for every allowed `n`. Python integers handle this.
### Examples
**Example 1**
```text
Input: n = 3
Output: 3
```
The ways are 1 + 1 + 1, 1 + 2 and 2 + 1.
**Example 2**
```text
Input: n = 5
Output: 8
```
With no two-step move there is 1 way (five single steps). With one two-step move among four moves there are 4 ways. With two two-step moves among three moves there are 3 ways.
**Example 3**
```text
Input: n = 46
Output: 2971215073
```
This answer is already larger than `2^31 - 1 = 2147483647`.
Overview: Count the distinct ordered sequences of one-step and two-step moves that climb a staircase of n steps and land exactly on the top step. This coding question tests building a counting argument over smaller staircases and handling answers that grow beyond 32-bit integers as n increases.
Read the full Goldman Sachs Quantitative Researcher interview experience this question came from
You stand at the bottom of a staircase with `n` steps. Each move climbs either one step or two steps. Return the number of distinct ways to reach the top, that is, to land exactly on step `n`.
A way is an ordered sequence of moves, each of size 1 or 2, whose sizes add up to exactly `n`. Sequences that use the same moves in a different order are different ways: climbing 1 then 2 differs from climbing 2 then 1. You may not climb past step `n`.
Implement `count_climb_ways(n)`, which returns this count as an integer.
### Constraints
- `1 <= n <= 70`
- The answer exceeds `2^31 - 1 = 2147483647` once `n >= 46` (for example, `n = 46` gives `2971215073`), but stays below `2^53` for every allowed `n`. Return a 64-bit integer: `long` in Java and `long long` in C++. A JavaScript number holds every answer exactly.
### Examples
**Example 1**
```text
Input: n = 3
Output: 3
```
The ways are 1 + 1 + 1, 1 + 2 and 2 + 1.
**Example 2**
```text
Input: n = 5
Output: 8
```
With no two-step move there is 1 way (five single steps). With one two-step move among four moves there are 4 ways. With two two-step moves among three moves there are 3 ways.
Constraints
- 1 <= n <= 70
- The answer exceeds 2^31 - 1 once n >= 46, but stays below 2^53 for every allowed n: use long in Java and long long in C++; JavaScript numbers are exact.
Examples
Input: (1,)
Expected Output: 1
Explanation: Minimum n: the only way is a single one-step move.
Input: (2,)
Expected Output: 2
Explanation: Smallest staircase that allows a two-step move: 1 + 1 and 2.
Hints
- Write out every way for n = 1, 2, 3 and 4 by hand and compare the counts.
- Order matters: 1 + 2 and 2 + 1 are different ways, so count sequences of moves, not just how many of each move size you use.
- Answers for n >= 46 do not fit in a 32-bit integer, so choose a result type that can hold values up to 2^53.