FunctionRacerProblemsRace

Lucky Toll Trips

MediumDynamic programmingPython, JavaScript, TypeScript, Java, C++

tolls is a grid of road tolls given as a list of rows, and a cell holding -1 is closed. A car drives from the top left cell to the bottom right cell, moving one cell right or one cell down at a time and never entering a closed cell. A trip is lucky when the sum of the tolls of all the cells it enters, the first and the last included, is divisible by k.

Return the number of lucky trips. If the start or the end cell is closed, return 0.

Example 1

tolls [[1,2,3],[4,5,6]]
k 3
returns 1

Of the three trips, only right, right, down totals a multiple of 3: 1 + 2 + 3 + 6 = 12.

Example 2

tolls [[2,-1,4],[3,1,5],[0,6,7]]
k 3
returns 2

Three trips avoid the closed cell. Two of them total 18, which is divisible by 3; the third totals 19.

Constraints

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Dynamic programming problems