Count Staircases Built from n Blocks with Strictly Increasing Step Heights
Company: eBay
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You have `n` identical unit blocks. A staircase is a row of one or more steps, each step a column of blocks, where every step has a positive height and each step is strictly taller than the step before it. Count how many different staircases use all `n` blocks exactly. A staircase made of a single step of height `n` also counts.
### Function Signature
```python
def count_staircases(n: int) -> int:
```
### Rules
- A staircase is described by its step heights from left to right, `h1 < h2 < ... < hk`, with `k >= 1`, every `hi >= 1`, and `h1 + h2 + ... + hk == n`.
- Two staircases are different when their lists of heights differ. Because the heights must strictly increase, the order of the steps is fixed, so a staircase is the same thing as a set of distinct positive integers that sum to `n`.
- The single step `[n]` counts as one staircase.
- Return the number of different staircases.
### Constraints
- `1 <= n <= 500`
- The answer exceeds `2^31 - 1` for the larger values of `n` in this range, so use a 64-bit or arbitrary-precision integer. For every `n` in the range, the answer is below `2^53`.
### Examples
**Example 1**
```text
Input: n = 1
Output: 1
```
The only staircase is a single step of height 1.
**Example 2**
```text
Input: n = 6
Output: 4
```
The staircases are `[6]`, `[1, 5]`, `[2, 4]` and `[1, 2, 3]`. `[3, 3]` is not allowed because the heights must strictly increase.
**Example 3**
```text
Input: n = 10
Output: 10
```
The staircases are `[10]`, `[1, 9]`, `[2, 8]`, `[3, 7]`, `[4, 6]`, `[1, 2, 7]`, `[1, 3, 6]`, `[1, 4, 5]`, `[2, 3, 5]` and `[1, 2, 3, 4]`.
Overview: Count how many staircases can be built from exactly n unit blocks when every step has a positive height, heights strictly increase, and a single step of height n also counts. It tests turning a combinatorial counting question into an efficient algorithm whose results grow beyond 32-bit integers.
Read the full eBay Machine Learning Engineer interview experience this question came from
You have `n` identical unit blocks. A staircase is a row of one or more steps, each step a column of blocks, where every step has a positive height and each step is strictly taller than the step before it. Count how many different staircases use all `n` blocks exactly. A staircase made of a single step of height `n` also counts.
A staircase is described by its step heights from left to right, `h1 < h2 < ... < hk`, with `k >= 1`, every `hi >= 1`, and `h1 + h2 + ... + hk == n`. Two staircases are different when their lists of heights differ. Because the heights must strictly increase, the order of the steps is fixed, so a staircase is the same thing as a set of distinct positive integers that sum to `n`.
Implement `count_staircases(n)` and return the number of different staircases.
**Example 1**
```text
Input: n = 6
Output: 4
```
The staircases are `[6]`, `[1, 5]`, `[2, 4]` and `[1, 2, 3]`. `[3, 3]` is not allowed because the heights must strictly increase.
**Example 2**
```text
Input: n = 10
Output: 10
```
The staircases are `[10]`, `[1, 9]`, `[2, 8]`, `[3, 7]`, `[4, 6]`, `[1, 2, 7]`, `[1, 3, 6]`, `[1, 4, 5]`, `[2, 3, 5]` and `[1, 2, 3, 4]`.
**Constraints**
- `1 <= n <= 500`
- The answer exceeds `2^31 - 1` for the larger values of `n` in this range, so return it as a 64-bit integer (`long` in Java, `long long` in C++).
- For every `n` in the range, the answer is below `2^53`, so it is exactly representable as a JavaScript number.
Constraints
- 1 <= n <= 500
- The answer exceeds 2^31 - 1 for the larger values of n in this range, so it must be returned as a 64-bit integer (long in Java, long long in C++).
- For every n in the range, the answer is below 2^53.
Examples
Input: (1,)
Expected Output: 1
Explanation: Minimum n: the only staircase is the single step [1].
Input: (2,)
Expected Output: 1
Explanation: Only the single step [2]; [1, 1] is rejected because heights must strictly increase.
Hints
- Because the heights must strictly increase, the order of the steps is forced: a staircase is determined entirely by which heights it uses.
- Each height from 1 to n can be used at most once, and no height can exceed n.
- Remember to count the single step [n], and use a 64-bit integer because the count passes 2^31 - 1 for larger n.