Routes With a Divisible Toll
Problem
A toll road network is a grid tolls of non-negative integers. A truck starts at the top-left cell and drives to the bottom-right cell, moving only right or down, and pays the toll of every cell it visits (both ends included).
The operator only accepts totals that are divisible by k. Return the number of routes whose total toll is divisible by k. The answer can be large, so return it modulo 1,000,000,007.
Example 1
- Input:
- tolls = [[4, 2, 3], [1, 7, 5]], k = 3
- Output:
- 1
The three routes cost 4+2+3+5 = 14, 4+2+7+5 = 18 and 4+1+7+5 = 17. Only 18 is divisible by 3.
Example 2
- Input:
- tolls = [[0, 0], [0, 0]], k = 5
- Output:
- 2
Both routes cost 0, and 0 is divisible by 5.
Constraints
- 1 ≤ tolls.length, tolls[0].length ≤ 100
- 0 ≤ tolls[r][c] ≤ 100
- 1 ≤ k ≤ 50
Hint
Show the first hint
Counting routes per cell is not enough: two routes into the same cell can have different totals. What do you need to know about a partial total?
Walkthrough
How to approach it
01Clarify before coding
- Is 0 divisible by k? Yes, a total of 0 counts.
- Can k be 1? Yes, then every route counts.
- Why the modulo? With 100 × 100 grids the number of routes is around 10^58.
02Brute force
Enumerate every route, sum its tolls and test divisibility.
Cost: Exponential in m + n; even the 2-D route-count DP alone cannot answer it, because it forgets the totals.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.