Skip to main content

LeetCode 2435. Paths in Matrix Whose Sum Is Divisible by K in F#

Published 1 min readMarkdown

URL

Paths in Matrix Whose Sum Is Divisible by K - LeetCode

Code

dotnet-study/fsharp/leetcode/challenge/202511/paths_in_matrix_whose_sum_is_divisible_by_key/main.fsx at master · syohex/dotnet-study

let numberOfPaths (grid: int[,]) (k: int) : int =
    let rows, cols = Array2D.length1 grid, Array2D.length2 grid
    let modulo = 1_000_000_007

    let getValue row col m dp =
        dp |> Map.tryFind (row, col, m) |> Option.defaultValue 0

    let rec numberOfPaths' row col dp =
        if row >= rows then
            Map.find (rows - 1, cols - 1, 0) dp
        elif col >= cols then
            numberOfPaths' (row + 1) 0 dp
        else
            let m = grid.[row, col] % k

            let dp =
                seq { 0 .. (k - 1) }
                |> Seq.fold
                    (fun acc i ->
                        let prev = (i + k - m) % k
                        let v1 = getValue (row - 1) col prev acc
                        let v2 = getValue row (col - 1) prev acc
                        let v = (v1 + v2) % modulo
                        Map.add (row, col, i) v acc)
                    dp

            numberOfPaths' row (col + 1) dp

    let dp = Map.empty |> Map.add (0, 0, grid.[0, 0] % k) 1
    numberOfPaths' 0 1 dp

No comments yet. Be the first to comment.

More from this blog