Katkat
Back

Count Ways to Reach Step n With a Given Set of Step Sizes

SquarepointData Scientist · Technical Screen
MediumData ScientistTechnical ScreenCoding & Algorithms

Last updated

From a Squarepoint technical screen: count the ordered sequences of moves that climb exactly n stairs when every move uses a step size from a given set. It tests careful counting of ordered choices, targets that cannot be reached, and the interviewer's follow-up about reducing the extra space the solution uses.

You are climbing a staircase with n steps, starting on the ground (step 0). Every move offers the same set of choices: you pick one of the allowed step sizes in steps and climb exactly that many steps. Return the number of distinct move sequences that end exactly on step n.

In the interview, a follow-up asked whether the extra space used by the solution could be reduced.

Function Signature

def count_ways(n: int, steps: list[int]) -> int:

Rules

  • Order matters: two sequences are different if they have different lengths or choose a different step size at some position, so 1 + 2 and 2 + 1 are different sequences.
  • The step sizes in a sequence must add up to exactly n.
  • Each allowed step size can be used any number of times, and steps may be given in any order.
  • If no sequence reaches step n exactly, return 0.

Constraints

  • 1 <= n <= 50
  • 1 <= len(steps) <= 50
  • The values in steps are distinct, and 1 <= steps[i] <= 50.
  • The answer is at most 2^49 (reached when n = 50 and every size from 1 to 50 is allowed). That exceeds the 32-bit signed range but stays below 2^53, so use 64-bit integers.

Examples

Example 1

Input: n = 4, steps = [1, 2]
Output: 5

The sequences are 1+1+1+1, 1+1+2, 1+2+1, 2+1+1 and 2+2.

Example 2

Input: n = 5, steps = [1, 3, 5]
Output: 5

The sequences are 1+1+1+1+1, 1+1+3, 1+3+1, 3+1+1 and 5.

Example 3

Input: n = 7, steps = [2, 4]
Output: 0

Every allowed size is even, so no sequence adds up to 7.