FastPrep
Problem · Array

Maximum Score with Prime Jumps

Learn this problem
● MediumMicrosoft logoMicrosoftINTERNOA
See Microsoft hiring insights

Problem statement

You are given an integer array cell representing a row of cells numbered from 0 to cell.length - 1. The value of cell[0] is always 0.

A player starts at cell 0 with a score of 0. On each move, the player may:

  • Move one cell to the right.
  • Move p cells to the right, where p is a prime number whose decimal representation ends in 3.

The player may not move beyond the final cell. Whenever the player lands on a cell, that cell's value is added to the score. The game ends when the player reaches cell cell.length - 1.

Return the maximum possible score. If cell contains only cell 0, return 0.

Function

maximumScore(cell: int[]) → long

Examples

Example 1

cell = [0,-10,-20,-30,50]return = 40

There are three ways to reach cell 4:

  • Jump 3 cells and then move 1 cell, scoring -30 + 50 = 20.
  • Move 1 cell and then jump 3 cells, scoring -10 + 50 = 40.
  • Move 1 cell four times, scoring -10 - 20 - 30 + 50 = -10.

The maximum possible score is 40.

Example 2

cell = [0,-100,-100,8]return = 8

Because 3 is prime and ends in 3, the player can jump directly from cell 0 to cell 3. Only cell[3] is added, so the score is 8.

Example 3

cell = [0,5,4,3,2,1]return = 15

Moving one cell at a time visits every positive-valued cell and gives 5 + 4 + 3 + 2 + 1 = 15. Taking a prime jump would skip positive values, so it cannot improve this score.

Constraints

  • 1 <= cell.length <= 10^4
  • cell[0] == 0
  • -10^9 <= cell[i] <= 10^9 for every valid index i.

More Microsoft problems

drafts saved locally
public long maximumScore(int[] cell) {
    // Write your code here
}
cell[0,-10,-20,-30,50]
expected40
checking account