Description
Count Islands With Total Value Divisible by K
MediumYou are given an m x n matrix grid and a positive integer k. An island is a group of positive integers (representing land) that are 4-directionally connected (horizontally or vertically).
The total value of an island is the sum of the values of all cells in the island.
Return the number of islands with a total value divisible by k.
Example 1:
Input: grid = [[0,2,1,0,0],[0,5,0,0,5],[0,0,1,0,0],[0,1,4,7,0],[0,2,0,0,8]], k = 5
Output: 2
Explanation:
The grid contains four islands. The islands highlighted in blue have a total value that is divisible by 5, while the islands highlighted in red do not.
Example 2:
Input: grid = [[3,0,3,0], [0,3,0,3], [3,0,3,0]], k = 3
Output: 6
Explanation:
The grid contains six islands, each with a total value that is divisible by 3.
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 10001 <= m * n <= 1050 <= grid[i][j] <= 1061 <= k <= 106
Solutions
Another fun exploration algorithm, simple enough.
/**
* @param {number[][]} grid
* @param {number} k
* @return {number}
*/
var countIslands = function(grid, k) {
const rows = grid.length;
const cols = grid[0].length;
let res = 0;
const explore = (row, col) => {
if (row < 0 || row >= rows || col < 0 || col >= cols || grid[row][col] === 0) {
return 0;
}
const val = grid[row][col];
grid[row][col] = 0;
return val +
explore(row, col + 1) +
explore(row + 1, col) +
explore(row, col - 1) +
explore(row - 1, col);
};
for (let row = 0; row < rows; row++) {
for (let col = 0; col < cols; col++) {
if (grid[row][col] !== 0) {
const sum = explore(row, col);
if (sum % k === 0) {
res++;
}
}
}
}
return res;
};