FastPrep
Problem · Dynamic Programming

Jump Game with Prime-3 Steps

● HardUberOA
See Uber hiring insights

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.

Examples
01 · 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.

02 · 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.

03 · 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.
More Uber problems
drafts saved locally
public int maxJumpScore(int[] arr) {
  // write your code here
}
arr[5, -100, 4, 10]
expected15
sign in to submit