The solution posted still requires O(n) calls to your random number generator. You can do it in something like O(log n) calls while still sticking to a single

The solution posted still requires O(n) calls to your random number generator. You can do it in something like O(log n) calls while still sticking to a single forward only pass. (But compared to reading the filesystem the rng calls were probably treated as free.)