Sha256: b0883440a54b2e3afe0123f1a0f336d3468bdbff25fccba5c52a9c5d310e4127
Contents?: true
Size: 987 Bytes
Versions: 8
Compression:
Stored size: 987 Bytes
Contents
let intCompare = (n1: int, n2: int) => {
if(n1 == n2) {
0
} else if(n1 > n2) {
1
} else {
-1
}
};
let findSmallestCoinsListMeetingTarget =
(cache: array(option(list(int))), coins: list(int), target: int)
: option(list(int)) => {
let findCoinsMeetingTargetMinusCoin = (coin) =>
if (target == coin) {
Some([coin]);
} else {
Belt.Option.map(cache[target - coin], (cs) => [coin, ...cs]);
};
List.filter((x) => x <= target, coins)
|> List.map(findCoinsMeetingTargetMinusCoin)
|> Belt.List.keepMap(_, (x) => x)
|> List.sort((xs, ys) => intCompare(List.length(xs), List.length(ys)))
|> Belt.List.head;
};
let makeChange = (target: int, coins: list(int)): option(list(int)) =>
switch(target) {
| 0 => Some([])
| _ when target < 0 => None
| _ =>
let cache = Array.make(target + 1, None);
for (i in 1 to target) {
cache[i] = findSmallestCoinsListMeetingTarget(cache, coins, i);
};
cache[target];
};
Version data entries
8 entries across 8 versions & 1 rubygems