Skip to content

Instantly share code, notes, and snippets.

@ulve
Last active November 11, 2017 13:10
Show Gist options
  • Save ulve/bb72fe8b875e79852765c04333f2ee0f to your computer and use it in GitHub Desktop.
Save ulve/bb72fe8b875e79852765c04333f2ee0f to your computer and use it in GitHub Desktop.
Find the smallest free number in a list
let rec minfrom = (a, n, xs) => {
let b = a + 1 + n/2;
let (us, vs) = List.partition(fun (x) => x < b, xs);
let m = List.length(us);
if(n == 0)
a
else if(m == b - a)
minfrom(b, n - m, vs)
else
minfrom(a, m, us)
};
let minfree = xs => {
minfrom(0, (List.length(xs)), xs)
};
[8, 23, 9, 0, 12, 11, 1, 10, 13, 7, 41, 4, 14, 21, 5, 17, 3, 19, 2, 6] |> minfree |> Js.log;
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment