Jump Game with Prime-3 Steps
Reported by candidates from Agoda's online assessment. Pattern, common pitfall, and the honest play if you blank under the timer.
The Agoda OA reported in June 2025 looks like a jump game, but the real work is a one-dimensional DP array with a precomputed list of allowed jump lengths. You start at index 0, you must land on the last city, and every city you touch adds or subtracts its value. Allowed moves are +1 or a prime ending in 3 (3, 13, 23, 43, 53...). With n up to 5000, the setup is small. If you blank on the recurrence mid-assessment, StealthCoder is the invisible safety net that reads the problem and hands you the solution.
The problem
You are given an integer array cities. Each value is the amount of money gained in that city when positive, or spent in that city when negative. You start in the first city, and its value is included in your total. From city index i, you may move only to the right. In one move, you may go to: the next city, at index i + 1; or city i + p, where p is a prime number whose units digit is 3. Every move must stay inside the array, and you must finish in the final city. Return the maximum possible net amount collected from every city you visit, including the first and final cities. Function maxJumpScore(cities: int[]) → int Examples Example 1 cities = [5,-100,4,10] return = 15 Jump directly from index 0 to index 3. The jump length 3 is prime and ends in 3, so the total is 5 + 10 = 15. Example 2 cities = [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 cities = [7] return = 7 The first city is already the final city, so the answer is its value. Constraints 1 <= cities.length <= 5000 -10000 <= cities[i] <= 10000 The first and final cities are always included in the total. A valid long jump is prime and has units digit 3.
Reported by candidates. Source: FastPrep
Pattern and pitfall
The data structure is a dp array where dp[i] is the best total collected when you end at city i. Set dp[0] = cities[0]. For each i, dp[i] = cities[i] + max(dp[i-1], dp[i-p]) over every valid p <= i. Sieve primes up to 5000 once, keep only those with p % 10 == 3, and loop over that short list per index. That's roughly n times a few hundred, which is fast. The common pitfall is greedy thinking. Skipping a big negative city looks tempting, but a jump can't always land where you want, so you need the full DP. Another trap is forgetting that 3 itself counts, or that 1 is not prime. Handle n = 1 by returning cities[0]. Use plain ints, since the sums stay small. If the recurrence slips away under pressure, StealthCoder can cover you live.
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 Agoda's OA.
Agoda 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 Agoda Jump Game with Prime-3 Steps problem?+
It's a linear DP over positions. dp[i] equals cities[i] plus the better of dp[i-1] or dp[i-p] for each allowed prime p ending in 3. Precompute those primes with a sieve once, then every index just scans that list.
How hard is this problem really?+
Medium at most. The prime twist sounds scary, but it only changes which offsets you try. If you've done Jump Game style DP or climbing stairs with custom steps, you already know the shape. The sieve is a few lines.
Why not just use a greedy approach?+
Greedy fails because values can be negative and jump lengths are restricted. Taking a locally good move may leave you unable to reach the final city efficiently. DP considers every legal predecessor, so it always finds the true maximum.
What edge cases should I test before submitting?+
Test a single-element array, which returns that value. Test length 2 and 3, where only +1 or the 3-jump work. Check all-negative arrays, since you still must include the first and last cities. Also confirm 3 is in your prime list and 1 is not.
How do I prep for this in 48 hours?+
Write the sieve and the DP once from scratch, then run the three examples by hand. Practice similar restricted-step DP problems so the recurrence feels automatic. Focus on the loop bounds, since off-by-one errors with i-p are the main way to lose points.