問題陳述

1. 給定一個整數(shù)N，N的階乘N!中末尾有多少個0阿浓？
2. N! 的二進(jìn)制表示中最低位1的位置？

問題1的O(N²)解法

如果N! = K x 10^M, K是不能被10整除的數(shù)择同。
M 表示 N!的末尾有M個0判帮。

可以看到，N!的末尾有多少個0裳仆，和N!的分解式中10的個數(shù)有關(guān)腕让。

對 N! 進(jìn)行質(zhì)因數(shù)分解 N! = (2^X) x (3^Y) x (5^Z)......。

因此M只和質(zhì)因數(shù)分解式中2的個數(shù)和5的個數(shù)有關(guān)歧斟。即 M = min(X, Z)

由于從1-N中纯丸，能被2整除的數(shù)出現(xiàn)的頻率 肯定大于 能被5整除的數(shù)出現(xiàn)的頻率。
因此静袖，M = Z;

因此得到我們的時間復(fù)雜度O(N²)樸素的解法：

public static int numOfZeroINFactorial_1(int N){
        int res=0;
        for(int i=1; i<=N; ++i){
            int j = i;
            while(j % 5 == 0){
                res++;
                j /= 5;
            }
        }
        return res;
    }

問題1的O(N)解法

k是正整數(shù)觉鼻， floor(N/k)表示 1,2,3，...., N中能被k整除的數(shù)的個數(shù)队橙。

證明：
假設(shè)1,2,3坠陈，...., N中有m個數(shù)可以被k整除，則共有
1k, 2k, 3k, ..., mk(mk<=N)個數(shù)可以被k整除捐康。顯然仇矾，m=floor(N / k) 就是正解。

因此解总，M = floor(N/5) + floor(N / 5²) + floor(N / 5³) + ... 0.
該式表示贮匕，N!中含有質(zhì)因數(shù)5的個數(shù)。

public static int numOfZeroINFactorial_2(int N){
        int res=0;
        while(N!=0){
            res += (N/5);
            N /= 5;
        }
        return res;
    }

問題2的O(N)解法1

問題分析

求解N! 的二進(jìn)制表示中最低位1的位置倾鲫。等價于 求解N!的二進(jìn)制表示中最后有多少個0. 原問題的解就是0的個數(shù)加1.

將 N! 進(jìn)行質(zhì)因數(shù)分解 N! = (2^X) x (3^Y) x (5^Z)......后粗合，質(zhì)因數(shù)2的個數(shù)就是N!的二進(jìn)制表示中最后的0的個數(shù)萍嬉。

N!中質(zhì)因數(shù)2的個數(shù)等于 floor(N/2) + floor(N / 2²) floor(N / 2³) + ... +0.

代碼如下：

public static int solution1(int N){
        int res=0;
        while(N!=0){
            res += (N >> 1);
            N >>= 1;
        }
        return res+1;
    }

問題2的O(N)解法2

N!中質(zhì)因數(shù)2的個數(shù)等于N減去N的二進(jìn)制表示中1的數(shù)目

證明：
N!中質(zhì)因數(shù)2的個數(shù)等于 floor(N/2) + floor(N / 2²) floor(N / 2³) + ... +0.

假設(shè)N=11011則
1101 + 110 + 11 + 1
=（1000 + 100 + 1）
+（100 + 10）
+（10 + 1）
+（1）
=（1000 + 100+ 10 + 1）+（100 + 10 + 1）+ 1
= 1111 + 111 + 1
=（10000 -1）+（1000 - 1）+（10-1）+（1-1）
= 11011 - N二進(jìn)制表示中1的個數(shù)

private static int numOne(int v){
        int num = 0;
        while(v!=0){
            v &= (v-1);
            num++;
        }
        return num;
    }
res = N - numOne(N);

擴(kuò)展問題1

給定整數(shù)N，判斷它是否是2的方冪隙疚。

N>0 && ( (N&(N-1))==0 )