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.)