paths-in-matrix-whose-sum-is-divisible-by-k

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given a 0-indexed <code>m x n</code> integer matrix <code>grid</code> and an integer <code>k</code>. You are currently at position <code>(0, 0)</code> and you want to reach position <code>(m - 1, n - 1)</code> moving only down or right.

Return the number of paths where the sum of the elements on the path is divisible by <code>k</code>. Since the answer may be very large, return it modulo <code>109 + 7</code>.

&nbsp;
Example 1:
<img src="https://assets.leetcode.com/uploads/2022/08/13/image-20220813183124-1.png" style="width: 437px; height: 200px;" />
<pre>
Input: grid = [[5,2,4],[3,0,5],[0,7,2]], k = 3
Output: 2
Explanation: There are two paths where the sum of the elements on the path is divisible by k.
The first path highlighted in red has a sum of 5 + 2 + 4 + 5 + 2 = 18 which is divisible by 3.
The second path highlighted in blue has a sum of 5 + 3 + 0 + 5 + 2 = 15 which is divisible by 3.
</pre>

Example 2:
<img src="https://assets.leetcode.com/uploads/2022/08/17/image-20220817112930-3.png" style="height: 85px; width: 132px;" />
<pre>
Input: grid = [[0,0]], k = 5
Output: 1
Explanation: The path highlighted in red has a sum of 0 + 0 = 0 which is divisible by 5.
</pre>

Example 3:
<img src="https://assets.leetcode.com/uploads/2022/08/12/image-20220812224605-3.png" style="width: 257px; height: 200px;" />
<pre>
Input: grid = [[7,3,4,9],[2,3,6,2],[2,3,7,0]], k = 1
Output: 10
Explanation: Every integer is divisible by 1 so the sum of the elements on every possible path is divisible by k.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>m == grid.length</code></li>
	<li><code>n == grid[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 5 * 104</code></li>
	<li><code>1 &lt;= m * n &lt;= 5 * 104</code></li>
	<li><code>0 &lt;= grid[i][j] &lt;= 100</code></li>
	<li><code>1 &lt;= k &lt;= 50</code></li>
</ul>

numberOfPaths

Paths in Matrix Whose Sum Is Divisible by K

Unique Paths

unique-paths

不同路径

Unique Paths II

unique-paths-ii

不同路径 II

Minimum Path Sum

minimum-path-sum

最小路径和

Dungeon Game

dungeon-game

地下城游戏

Cherry Pickup

cherry-pickup

摘樱桃

Shortest Path in Binary Matrix

shortest-path-in-binary-matrix

二进制矩阵中的最短路径

Minimum Cost Homecoming of a Robot in a Grid

minimum-cost-homecoming-of-a-robot-in-a-grid

网格图中机器人回家的最小代价

Check if There is a Path With Equal Number of 0's And 1's

check-if-there-is-a-path-with-equal-number-of-0s-and-1s

检查是否有路径经过相同数量的 0 和 1

Array

Dynamic Programming

Matrix

给你一个下标从 0&nbsp;开始的&nbsp;<code>m x n</code>&nbsp;整数矩阵&nbsp;<code>grid</code>&nbsp;和一个整数&nbsp;<code>k</code>&nbsp;。你从起点&nbsp;<code>(0, 0)</code>&nbsp;出发，每一步只能往 下&nbsp;或者往 右&nbsp;，你想要到达终点&nbsp;<code>(m - 1, n - 1)</code>&nbsp;。

请你返回路径和能被 <code>k</code>&nbsp;整除的路径数目，由于答案可能很大，返回答案对&nbsp;<code>109 + 7</code>&nbsp;取余&nbsp;的结果。

&nbsp;

示例 1：

<img src="https://assets.leetcode.com/uploads/2022/08/13/image-20220813183124-1.png" style="width: 437px; height: 200px;">

<pre>输入：grid = [[5,2,4],[3,0,5],[0,7,2]], k = 3
输出：2
解释：有两条路径满足路径上元素的和能被 k 整除。
第一条路径为上图中用红色标注的路径，和为 5 + 2 + 4 + 5 + 2 = 18 ，能被 3 整除。
第二条路径为上图中用蓝色标注的路径，和为 5 + 3 + 0 + 5 + 2 = 15 ，能被 3 整除。
</pre>

示例 2：
<img src="https://assets.leetcode.com/uploads/2022/08/17/image-20220817112930-3.png" style="height: 85px; width: 132px;">
<pre>输入：grid = [[0,0]], k = 5
输出：1
解释：红色标注的路径和为 0 + 0 = 0 ，能被 5 整除。
</pre>

示例 3：
<img src="https://assets.leetcode.com/uploads/2022/08/12/image-20220812224605-3.png" style="width: 257px; height: 200px;">
<pre>输入：grid = [[7,3,4,9],[2,3,6,2],[2,3,7,0]], k = 1
输出：10
解释：每个数字都能被 1 整除，所以每一条路径的和都能被 k 整除。
</pre>

&nbsp;

提示：

<ul>
	<li><code>m == grid.length</code></li>
	<li><code>n == grid[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 5 * 104</code></li>
	<li><code>1 &lt;= m * n &lt;= 5 * 104</code></li>
	<li><code>0 &lt;= grid[i][j] &lt;= 100</code></li>
	<li><code>1 &lt;= k &lt;= 50</code></li>
</ul>