Katkat
Back

Count paths with prime-ending jumps

UberSoftware Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

This question evaluates a candidate's ability to design and implement dynamic programming for counting paths, combining combinatorial reasoning with modular arithmetic and handling step-size constraints tied to primes ending in digit 3.

You are given an integer n representing the top of a staircase, where you start at step 0 and want to land exactly on step n.

In one move, you may jump:

  • exactly 1 step, or
  • any prime number of steps whose decimal representation ends with the digit 3 (for example: 3, 13, 23, 43).

Count how many distinct sequences of jumps allow you to reach step n exactly. Since the answer can be large, return it modulo 1,000,000,007.

A dynamic programming solution is expected. You may assume 1 <= n <= 100000.