3 ms·
> How would you find (n-1)! given n!? If you want to think a little more: You are given a value v, which you are told is n! for some n, which you are not told
by cbd1984 12y ago
> How would you find (n-1)! given n!?
If you want to think a little more:
You are given a value v, which you are told is n! for some n, which you are not told. Find a general algorithm to produce (n-1)!.
I have an algorithm which, I fear, may not have the most efficient running time.
- panic 12y agoIf you have n! in binary, count the number of zeros at the end of its binary expansion and call this count k. The number k+1 approximates n relatively closely (the error n-k is the number of ones in n's binary expansion—see http://www.cut-the-knot.org/blue/LegendresTheorem.shtml http://www.cut-the-knot.org/blue/LegendresTheorem.shtml).