LeetCode 3133. Minimum Array End in F#

URL

https://leetcode.com/problems/minimum-array-end/description/?envType=daily-question&envId=2024-11-09

Code

https://github.com/syohex/dotnet-study/blob/master/fsharp/leetcode/challenge/202411/minimum_array_end/main.fsx

let toBits (n: int) : int list =
    let rec toBits' n acc =
        if n = 0 then acc else toBits' (n / 2) ((n % 2) :: acc)

    toBits' n []

let minEnd (n: int) (x: int) : int64 =
    let rec minEnd' xBits nBits acc =
        match xBits, nBits with
        | [], [] ->
            acc
            |> List.rev
            |> List.fold (fun acc n -> acc * 2L + int64 n) 0L
        | _, [] -> failwith "never reach here"
        | [], h :: t -> minEnd' [] t (h :: acc)
        | h1 :: t1, h2 :: t2 ->
            if h1 = 1 then
                minEnd' t1 nBits (1 :: acc)
            else
                minEnd' t1 t2 (h2 :: acc)

    let xBits = toBits x
    let nBits = toBits (n - 1)
    minEnd' xBits nBits []