Jump Game with Prime-3 Steps
Reported by candidates from Uber's online assessment. Pattern, common pitfall, and the honest play if you blank under the timer.
Uber reportedly served this one in June 2026, and the detail that trips people is right in the statement: you can jump 1 step or a prime step ending in 3, and 33, 63 and 93 don't count. It's a maximum path sum on a line, so it's dynamic programming wearing a prime-number costume. Arrays go up to 100000 entries, so a sloppy approach dies fast. If you're taking this OA in the next day or two, you need the recurrence and the prime precompute, nothing more. StealthCoder sits invisibly on your screen as a safety net if your mind goes blank mid-assessment.
The problem
You are given an integer array arr. You start at index 0, and the score at the starting index is already included in your total. From an index i, you may move only to the right. In one move, you can jump to either i + 1 or i + p, where p is a prime number whose last digit is 3, such as 3, 13, 23, 43, or 53. Composite numbers such as 33, 63, and 93 are not valid jump lengths. Every jump must stay inside the array. You must finish exactly at index arr.length - 1. Return the maximum possible sum of the values at every index you land on, including both the start and the end. Function maxJumpScore(arr: int[]) → int Examples Example 1 arr = [5, -100, 4, 10] return = 15 Jump from index 0 to index 3 using a valid 3-step jump. The total is 5 + 10 = 15. Example 2 arr = [4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 20] return = 24 Jump directly from index 0 to index 13. The jump length 13 is prime and ends in 3, so the total is 4 + 20 = 24. Example 3 arr = [7] return = 7 The starting index is already the last index. Constraints 1 <= arr.length <= 100000 -10000 <= arr[i] <= 10000 The start and end indices are always included in the score. A valid prime-3 jump length must be prime and must have units digit 3.
Reported by candidates. Source: FastPrep
Pattern and pitfall
Define dp[i] as the best score landing on index i. dp[0] = arr[0]. For each i, dp[i] = arr[i] + max(dp[i-1], dp[i-p]) over every valid p <= i. Valid p are primes with last digit 3, so sieve primes up to n once and keep only those ending in 3. The answer is dp[n-1]. The pitfall is complexity. Primes ending in 3 are about a quarter of all primes, so the inner loop is roughly n/(4 ln n) per index. That's fine in practice but don't test primality per jump with trial division inside the loop. Another trap is initializing with 0 instead of negative infinity. Negative values mean you can't treat unreachable states as zero. Index i-1 is always reachable, so it's mostly safe, but be careful anyway. Single-element arrays return arr[0]. If the live OA makes you freeze on the recurrence, StealthCoder is the hedge that hands you the clean DP.
If you see this problem in your OA tomorrow, the play is to recognize the pattern in 30 seconds. StealthCoder buys you that recognition.
You can drill Jump Game with Prime-3 Steps cold, or you can hedge it. StealthCoder runs invisibly during screen share and surfaces a working solution in under 2 seconds. The proctor sees the IDE. They don't see what's behind it. Built by an Amazon engineer who passed his OA cold and still thinks the filter is broken.
Get StealthCoderRelated leaked OAs
You've seen the question.
Make sure you actually pass Uber's OA.
Uber reuses patterns across OAs. Built by an Amazon engineer who passed his OA cold and still thinks the filter is broken. Works on HackerRank, CodeSignal, CoderPad, and Karat.
Jump Game with Prime-3 Steps FAQ
What's the trick in the Uber Jump Game with Prime-3 Steps?+
It's a forward DP where dp[i] = arr[i] + max over dp[i-1] and dp[i-p] for each valid prime p. Sieve primes once, filter those ending in 3, and reuse the list. The prime rule is just a fancy way of defining allowed jump lengths.
How do I generate the valid jump lengths?+
Run a sieve of Eratosthenes up to arr.length - 1, then keep primes where p % 10 == 3. That gives 3, 13, 23, 43, 53 and so on. Composites like 33, 63 and 93 are removed by the sieve automatically.
Will a greedy approach work here?+
No. Negative values mean the locally best jump can cost you later, as in example 1 where skipping a -100 with a 3-step jump wins. You need DP to compare every reachable predecessor, not pick the biggest next value.
What's the time complexity and will it pass 100000 elements?+
Sieve is O(n log log n). The DP is O(n times k), where k is the count of valid primes below n, roughly n/(4 ln n) at most. That's fine for n up to 100000 in a compiled or reasonably fast language.
How do I prepare for this in 48 hours?+
Write the DP once from scratch: sieve, filter by last digit, loop with max of two predecessors. Test the three examples, including the single-element case. Then do a couple of similar jump-game DP problems so the recurrence feels automatic under pressure.