FastPrepJump Game with Prime-3 Steps

Jump Game with Prime-3 Steps

Agoda logoAgoda● MediumFULLTIMEOA
Learn

Problem statement

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.

More Agoda problems

See Agoda hiring insights
public int maxJumpScore(int[] cities) {
  // write your code here
}
cities[5,-100,4,10]
expected15
Checking account…