Sha256: 6c53469b74e9e5f94694478ff8d45542e986725bc67e65184773ce33b68140eb
Contents?: true
Size: 803 Bytes
Versions: 42
Compression:
Stored size: 803 Bytes
Contents
open Base
let find_smallest_coins_list_meeting_target (cache: int list option array) (coins: int list) (target: int): int list option =
let find_coins_meeting_target_minus_coin coin =
if target = coin
then Some [coin]
else cache.(target - coin) |> Option.map ~f:(List.cons coin) in
List.filter coins ~f:(fun x -> x <= target)
|> List.map ~f:find_coins_meeting_target_minus_coin
|> List.filter_map ~f:(Fn.id)
|> List.sort ~compare:(fun xs ys -> Int.compare (List.length xs) (List.length ys))
|> List.hd
let make_change ~target ~coins = match target with
| 0 -> Some []
| _ when target < 0 -> None
| _ ->
let cache = Array.create ~len:(target+1) None in
for i = 1 to target do
cache.(i) <- find_smallest_coins_list_meeting_target cache coins i
done;
cache.(target)
Version data entries
42 entries across 42 versions & 1 rubygems