← 返回 uber 的题目列表Reachability with restricted backward moves and prime-step jumps (digit contains 3)
类型：online_judge
Problem: Reachability / minimum steps with restricted moves
Given a non-negative integer n, you start at position 0 on a number line and want to reach position n.
In one move, from position i you may:
Move backward by 1: go to i - 1 (allowed only if i - 1 >= 0).
Jump forward by choosing a step p such that p is a prime number and its decimal representation contains digit 3 (e.g., 3, 13, 23, 31, 43, ...). Then go to i + p (allowed only if i + p <= n).
Compute the minimum number of moves to reach n from 0. If it is impossible, output -1.
Input
One integer n.
Output
One integer: the minimum moves, or -1 if unreachable.
Constraints
(Not provided in the interview summary; please add if remembered.)
Examples
Input:
6
Output:
2
Because 0 -> 3 -> 6.
Example
Input
0
Output
0