{"id":9854,"date":"2022-10-10T18:04:27","date_gmt":"2022-10-11T01:04:27","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=9854"},"modified":"2022-10-10T18:09:30","modified_gmt":"2022-10-11T01:09:30","slug":"leetcode-2435-paths-in-matrix-whose-sum-is-divisible-by-k","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-2435-paths-in-matrix-whose-sum-is-divisible-by-k\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2435.\u00a0Paths in Matrix Whose Sum Is Divisible by K"},"content":{"rendered":"\n<figure class=\"wp-block-embed is-type-video is-provider-youtube wp-block-embed-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 2435. Paths in Matrix Whose Sum Is Divisible by K - \u5237\u9898\u627e\u5de5\u4f5c EP403\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/Gj8mvPsRkBI?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<p>You are given a&nbsp;<strong>0-indexed<\/strong>&nbsp;<code>m x n<\/code>&nbsp;integer matrix&nbsp;<code>grid<\/code>&nbsp;and an integer&nbsp;<code>k<\/code>. You are currently at position&nbsp;<code>(0, 0)<\/code>&nbsp;and you want to reach position&nbsp;<code>(m - 1, n - 1)<\/code>&nbsp;moving only&nbsp;<strong>down<\/strong>&nbsp;or&nbsp;<strong>right<\/strong>.<\/p>\n\n\n\n<p>Return<em>&nbsp;the number of paths where the sum of the elements on the path is divisible by&nbsp;<\/em><code>k<\/code>. Since the answer may be very large, return it&nbsp;<strong>modulo<\/strong>&nbsp;<code>10<sup>9<\/sup>&nbsp;+ 7<\/code>.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2022\/08\/13\/image-20220813183124-1.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> grid = [[5,2,4],[3,0,5],[0,7,2]], k = 3\n<strong>Output:<\/strong> 2\n<strong>Explanation:<\/strong> There are two paths where the sum of the elements on the path is divisible by k.\nThe first path highlighted in red has a sum of 5 + 2 + 4 + 5 + 2 = 18 which is divisible by 3.\nThe second path highlighted in blue has a sum of 5 + 3 + 0 + 5 + 2 = 15 which is divisible by 3.\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2022\/08\/17\/image-20220817112930-3.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> grid = [[0,0]], k = 5\n<strong>Output:<\/strong> 1\n<strong>Explanation:<\/strong> The path highlighted in red has a sum of 0 + 0 = 0 which is divisible by 5.\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2022\/08\/12\/image-20220812224605-3.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> grid = [[7,3,4,9],[2,3,6,2],[2,3,7,0]], k = 1\n<strong>Output:<\/strong> 10\n<strong>Explanation:<\/strong> Every integer is divisible by 1 so the sum of the elements on every possible path is divisible by k.\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>m == grid.length<\/code><\/li><li><code>n == grid[i].length<\/code><\/li><li><code>1 &lt;= m, n &lt;= 5 * 10<sup>4<\/sup><\/code><\/li><li><code>1 &lt;= m * n &lt;= 5 * 10<sup>4<\/sup><\/code><\/li><li><code>0 &lt;= grid[i][j] &lt;= 100<\/code><\/li><li><code>1 &lt;= k &lt;= 50<\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: DP<\/strong><\/h2>\n\n\n\n<figure class=\"wp-block-image size-full\"><a href=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2022\/10\/2435-ep403-1.png\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2022\/10\/2435-ep403-1.png\" alt=\"\" class=\"wp-image-9858\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2022\/10\/2435-ep403-1.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2022\/10\/2435-ep403-1-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2022\/10\/2435-ep403-1-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/a><\/figure>\n\n\n\n<figure class=\"wp-block-image size-full\"><a href=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2022\/10\/2435-ep403-2.png\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2022\/10\/2435-ep403-2.png\" alt=\"\" class=\"wp-image-9859\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2022\/10\/2435-ep403-2.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2022\/10\/2435-ep403-2-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2022\/10\/2435-ep403-2-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/a><\/figure>\n\n\n\n<figure class=\"wp-block-image size-full\"><a href=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2022\/10\/2435-ep403-3.png\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2022\/10\/2435-ep403-3.png\" alt=\"\" class=\"wp-image-9861\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2022\/10\/2435-ep403-3.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2022\/10\/2435-ep403-3-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2022\/10\/2435-ep403-3-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/a><\/figure>\n\n\n\n<p>Let dp[i][j][r] := # of paths from (0,0) to (i,j) with path sum % k == r.<br><br>init: dp[0][0][grid[0][0] % k] = 1<\/p>\n\n\n\n<p>dp[i][j][(r + grid[i][j]) % k] = dp[i-1][j][r] + dp[i][j-1][r]<\/p>\n\n\n\n<p>ans = dp[m-1][n-1][0]<\/p>\n\n\n\n<p>Time complexity: O(m*n*k)<br>Space complexity: O(m*n*k) -&gt; O(n*k)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int numberOfPaths(vector<vector<int>>& grid, int k) {\n    const int kMod = 1e9 + 7;\n    const int m = grid.size();\n    const int n = grid[0].size();\n    vector<vector<vector<int>>> dp(m, vector<vector<int>>(n, vector<int>(k)));\n    dp[0][0][grid[0][0] % k] = 1;\n    for (int i = 0; i < m; ++i)\n      for (int j = 0; j < n; ++j) {\n        if (i == 0 &#038;&#038; j == 0) continue;\n        for (int r = 0; r < k; ++r)\n          dp[i][j][(r + grid[i][j]) % k] = \n            ((j ? dp[i][j - 1][r] : 0) + (i ? dp[i - 1][j][r] : 0)) % kMod;          \n      }\n    return dp[m - 1][n - 1][0];\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<p>Related Problems:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><a href=\"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-62-unique-paths\/\" data-type=\"post\" data-id=\"187\">\u82b1\u82b1\u9171 LeetCode 62. Unique Paths<\/a><\/li><\/ul>\n","protected":false},"excerpt":{"rendered":"<p>You are given a&nbsp;0-indexed&nbsp;m x n&nbsp;integer matrix&nbsp;grid&nbsp;and an integer&nbsp;k. You are currently at position&nbsp;(0, 0)&nbsp;and you want to reach position&nbsp;(m &#8211; 1, n &#8211; 1)&nbsp;moving&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[46],"tags":[18,278,217,275],"class_list":["post-9854","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","tag-dp","tag-grid","tag-hard","tag-paths","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9854","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=9854"}],"version-history":[{"count":5,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9854\/revisions"}],"predecessor-version":[{"id":9864,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9854\/revisions\/9864"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=9854"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=9854"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=9854"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}