Solve rand7

Write a random number generator for [0,7) using only a random number generator
for [0,5). Ensure the results are uniformly distributed.

1 files changed, 22 insertions, 0 deletions

diff --git a/scratch/facebook/moderate/rand7.py b/scratch/facebook/moderate/rand7.py
new file mode 100644
index 000000000000..19a96ed77b51
--- /dev/null
+++ b/scratch/facebook/moderate/rand7.py
@@ -0,0 +1,22 @@
+# Define a function, rand7, that generates a random number [0,7), using only
+# rand5, which generates a random number [0,5).
+
+import random
+from collections import Counter
+
+# Returns [0,4]
+def rand5():
+    return random.randint(0,4)
+
+def rand4():
+    x = rand7()
+    if x >= 4:
+        return rand4()
+    return x
+
+# Return [0,6]
+def rand7():
+    return sum(rand5() for _ in range(7)) % 7
+
+c = Counter([rand4() for _ in range(100000)])
+print(c)