32 Factorial Number

kamia

先找到要求值的上界，然后用二分法

1.     public static long findM(long n) {
   
2.         int i = 0;
   
3.         // First, find upper bound
   
4.         while(trailingZeros((long) Math.pow(2, i)) < n) {
   
5.             i++;
   
6.         }
   
7.         long left = 0, right = (long) Math.pow(2, i);
   
8.         // binary search find smallest valid one
   
9.         while(left <= right) {
   
10.             long mid = left + (right-left)/2;
    
11.             long zeros = trailingZeros(mid);
    
12.             if(zeros >= n) {
    
13.                 right = mid - 1;
    
14.             } else {
    
15.                 left = mid + 1;
    
16.             }
    
17.         }
    
18.         return left;
    
19.     }
    
20. 
    
21.     private static long trailingZeros(long n) {
    
22.         long cnt = 0, base = 5;
    
23.         while(n/base != 0) {
    
24.             cnt += n / base;
    
25.             base *= 5;
    
26.         }
    
27.         return cnt;
    
28.     }

复制代码

landscape1250

多谢