1class Solution {
2    private int rows;                  // Number of rows in the grid
3    private int cols;                  // Number of columns in the grid
4    private int[][] grid;              // Reference to the input grid
5    private final int[] dirOffsets = {-1, 0, 1, 0, -1}; // Direction offsets for 4 directions (up, right, down, left)
6
7    // Main method to count islands where the sum of island cells is divisible by k
8    public int countIslands(int[][] grid, int k) {
9        this.rows = grid.length;
10        this.cols = grid[0].length;
11        this.grid = grid;
12        int islandCount = 0;
13
14        for (int i = 0; i < rows; ++i) {
15            for (int j = 0; j < cols; ++j) {
16                // If the current cell is land (positive) and the sum of the island is divisible by k
17                if (grid[i][j] > 0 && dfs(i, j) % k == 0) {
18                    islandCount++;
19                }
20            }
21        }
22        return islandCount;
23    }
24
25    // Depth-First Search to compute the sum of values in an island and mark them as visited
26    private long dfs(int row, int col) {
27        long sum = grid[row][col]; // Store the value of the current cell
28        grid[row][col] = 0;        // Mark the cell as visited by setting it to 0
29
30        // Explore all 4 directions: up, right, down, left
31        for (int d = 0; d < 4; ++d) {
32            int nextRow = row + dirOffsets[d];
33            int nextCol = col + dirOffsets[d + 1];
34            // Check bounds and whether the neighboring cell is part of the island
35            if (nextRow >= 0 && nextRow < rows && nextCol >= 0 && nextCol < cols && grid[nextRow][nextCol] > 0) {
36                sum += dfs(nextRow, nextCol); // Accumulate the sum recursively
37            }
38        }
39        return sum;
40    }
41}
42

1class Solution {
2public:
3    // Counts the number of islands whose sum of values is divisible by k
4    int countIslands(std::vector<std::vector<int>>& grid, int k) {
5        int rows = grid.size();
6        int cols = grid[0].size();
7        std::vector<int> directions = {-1, 0, 1, 0, -1}; // for navigating four adjacent cells
8
9        // Recursive DFS lambda to compute island sum.
10        auto dfs = [&](auto&& self, int x, int y) -> long long {
11            long long sum = grid[x][y];    // start sum with current cell's value
12            grid[x][y] = 0;                // mark cell as visited by setting to 0
13
14            // Explore all 4 directions (up, right, down, left)
15            for (int d = 0; d < 4; ++d) {
16                int newX = x + directions[d];
17                int newY = y + directions[d + 1];
18
19                // Check bounds and whether cell is part of the current island
20                if (newX >= 0 && newX < rows && newY >= 0 && newY < cols && grid[newX][newY]) {
21                    sum += self(self, newX, newY);
22                }
23            }
24            return sum;
25        };
26
27        int islandCount = 0;
28
29        // Traverse every cell in the grid
30        for (int x = 0; x < rows; ++x) {
31            for (int y = 0; y < cols; ++y) {
32                // If cell is non-zero, it's a new island
33                if (grid[x][y]) {
34                    long long islandSum = dfs(dfs, x, y);
35                    // If the island's sum is divisible by k, increment count
36                    if (islandSum % k == 0) {
37                        ++islandCount;
38                    }
39                }
40            }
41        }
42        return islandCount;
43    }
44};
45

1/**
2 * Counts the number of islands in a grid where the sum of the island's cell values is divisible by k.
3 * @param grid - A 2D array of numbers representing the grid.
4 * @param k - The divisor for the sum of each island's cells.
5 * @returns The number of islands whose total values are divisible by k.
6 */
7function countIslands(grid: number[][], k: number): number {
8    const rows = grid.length;
9    const cols = grid[0].length;
10
11    // Directions for moving up, right, down, left
12    const directions = [-1, 0, 1, 0, -1];
13
14    /**
15     * Performs a DFS to visit all cells in the current island and returns their sum.
16     * @param row - The current row index.
17     * @param col - The current column index.
18     * @returns The sum of this island's cells.
19     */
20    function dfs(row: number, col: number): number {
21        let total = grid[row][col];
22        // Mark the cell as visited by setting to 0
23        grid[row][col] = 0;
24
25        // Explore all four directions
26        for (let d = 0; d < 4; d++) {
27            const newRow = row + directions[d];
28            const newCol = col + directions[d + 1];
29
30            // Continue DFS if the adjacent cell is within bounds and has a positive value
31            if (
32                newRow >= 0 && newRow < rows &&
33                newCol >= 0 && newCol < cols &&
34                grid[newRow][newCol] > 0
35            ) {
36                total += dfs(newRow, newCol);
37            }
38        }
39        return total;
40    }
41
42    let islandCount = 0;
43
44    // Traverse each cell in the grid
45    for (let row = 0; row < rows; row++) {
46        for (let col = 0; col < cols; col++) {
47            // Start DFS if the cell is positive (unvisited land)
48            if (grid[row][col] > 0) {
49                // Compute sum of island and check if it's divisible by k
50                if (dfs(row, col) % k === 0) {
51                    islandCount++;
52                }
53            }
54        }
55    }
56
57    return islandCount;
58}
59