title: Creating a random number generator from a coin toss
body: <p>Yesterday i had this interview question, which I couldn't fully answer:</p>
  
  <p>Given a function <code>f() = 0 or 1</code> with a perfect 1:1 distribution, create a function <code>f(n) = 0, 1, 2, ..., n-1</code> each with probability 1/n</p>
  
  <p>I could come up with a solution for if n is a natural power of 2, ie use <code>f()</code> to generate the bits of a binary number of <code>k=ln_2 n</code>. But this obviously wouldn't work for, say, n=5 as this would generate <code>f(5) = 5,6,7</code> which we do not want.</p>
  
  <p>Does anyone know a solution?</p>