Count paths with prime-ending jumps
Company: Uber
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
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`.
Quick Answer: 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.
Count sequences from step 0 to n using jumps of 1 or prime lengths ending in digit 3, modulo 1e9+7.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: (3,)
Expected Output: 2
Explanation: Either 1+1+1 or 3.
Input: (5,)
Expected Output: 4
Explanation: Prime-ending jump 3 plus ones.
Input: (13,)
Expected Output: 89
Explanation: Includes jump 13.
Input: (1,)
Expected Output: 1
Explanation: Only one step.
Hints
- Choose a representation that makes the requested operation direct.
- Handle empty inputs and boundary cases first.