How should I practice Count Staircases with Strictly Increasing Steps?

Start by reading the full statement, solve the visible examples, then compare the pattern against related eBay onsite interview problems in FastPrep.

Is Count Staircases with Strictly Increasing Steps associated with eBay?

FastPrep tags this as a eBay onsite interview coding practice problem when the problem catalog has that company and stage context.

Count Staircases with Strictly Increasing Steps

eBay● MediumFULLTIMEONSITE INTERVIEW

Problem statement

You have n identical unit blocks. A staircase is a row of one or more steps. Each step has a positive integer height, and the heights must strictly increase from left to right.

A staircase must use all n blocks, so its step heights add up to exactly n. A staircase with just one step of height n also counts.

Return the number of different staircases you can build. Two staircases are different when their lists of step heights are different.

Function

countStaircases(n: int) → long

Examples

Example 1

n = 5return = 3

The staircases that use all 5 blocks are [5], [1,4], and [2,3]. A list such as [1,1,3] is not allowed because the heights do not strictly increase.

Example 2

n = 10return = 10

The 10 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].

Example 3

n = 1return = 1

With one block, the only staircase is a single step of height 1.

Constraints

1 <= n <= 500
The answer fits in a signed 64-bit integer.