PreimageSizeOfFactorialZeroesFunction [source code]
public class PreimageSizeOfFactorialZeroesFunction {
static
/******************************************************************************/
class Solution {
public int preimageSizeFZF(int K) {
return count (K) - count (K - 1);
}
int count (int K) {
if (K < 0)
return 0;
int lo = K + 1, hi = 5 * (K + 1) + 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
int mid_zeros = f (mid);
if (mid_zeros <= K)
lo = mid + 1;
else
hi = mid - 1;
}
return lo;
}
int f (int x) {
return x == 0 ? 0 : x / 5 + f (x / 5);
}
}
/******************************************************************************/
public static void main(String[] args) {
PreimageSizeOfFactorialZeroesFunction.Solution tester = new PreimageSizeOfFactorialZeroesFunction.Solution();
int[] inputs = {
0, 5,
3, 5,
};
for (int i = 0; i < inputs.length / 2; i++) {
System.out.println (Printer.separator ());
int K = inputs[2 * i], ans = inputs[2 * i + 1], output = tester.preimageSizeFZF (K);
System.out.printf ("%d -> %s, expected: %d\n",
K, Printer.wrap (output + "", output == ans ? 92 : 91), ans
);
}
}
}
感觉好像会写; 这题是战略失误, 如果先看这题就好了; 这题好像之前在CHH上面看他们闲聊的时候看到过的;
最后想了想, 这题之所以能成为hard, 一个是数学分析的部分确实挺难的, 另外一个是根据问题得到这个分析之后, 还要能够用看到linear search就想到用binary search优化的直觉;
最后自己写了上面这个算法, 没想到这个二分还没有那么好解决; 我因为想要把awice的对range的判断给加进去, 所以最后这个二分设计的时候比uwi那个要稍微复杂一点;
首先, 我们可以确定, 如果要求有K个0, 那么x的范围是[K, 5K+1], 这个是下面editorial的时候已经讨论过的了;
然后我们看这个二分找的是什么, 因为要采用difference的思路, 所以最后我这里, 二分找的实际上是0的数量大于K的第一个; 也就是说, 比如我们主函数的参数是3, 那么我们就先找到有4个0最小的这一个, 也就是20, 然后是有3个0的最小的一个, 也就是15. 这里这个count(K), 返回的就是有K+1个0的最小的一个数字;
知道这里, 你就应该小心你count(K)里面, 给的初始范围是多少了: 你要找的是一个有K+1个0的! 所以最后给的初始范围应该是[K + 1, 5(K+1) + 1].
当然为了保险, 你可以降低下限;
最后发现一个问题, 就是发现这个函数对于K=-1的时候处理有点问题, 所以直接当成特殊情况处理掉就行了;
另外, 这个find the first nummber that is >target的二分, 实际实现也就简单, 跟以前总结过的一样, 就是等于的时候, hit的时候, 要考虑好怎么处理: 这里因为是要找大的, 所以等于的时候向右就行了; 最后lo直接就是你要的结果;
最后速度是4ms (NA).
另外, 关于这种first greater的二分的一个总结:
editorial
Approach #1: Binary Search [Accepted]
最后好像在类似uwi的那个做法的基础上面, 更进一步;
class Solution {
public int preimageSizeFZF(int K) {
int lo = K, hi = 10*K + 1;
while (lo < hi) {
int mi = lo + (hi - lo) / 2;
int zmi = zeta(mi);
if (zmi == K) return 5;
else if (zmi < K) lo = mi + 1;
else hi = mi;
}
return 0;
}
public int zeta(int x) {
if (x == 0) return 0;
return x/5 + zeta(x/5);
}
}
专门定义一个recursive的zeta函数来count ending zero, 也是一个不错的点子;
binary search的写法比uwi的稍微正常一点; uwi这个binary search的风格以前在三分地里面见过, 很多人为了避免写出来的二分不terminate, 直接最后在interval的length是1的时候就terminate掉这个循环;
How do you know the range is [K, 10*K+1]?
x/5 <= zeta(x) <= x.
这个暂时不理解, 回头重新思考了一下, 发现了他这里跟uwi的做法的一个很大的区别, uwi的做法搜索的实际上是x!, 他这里搜索的是x; 比如当K等于3的时候:
lo:(3), hi:(31), mid:(17), zmi:(3)
一个循环就结束了;
再回头重新看他这里的zeta的实现, 比如17是x, 最后的结果就是17 / 5 + 0 = 3. 还真的就是正确的结果, 但是这个是为什么呢?
不对, uwi的做法搜索的其实也是x; 要说uwi的做法跟awice这里的做法最大的区别, 无非就是contest当中uwi没有高兴去提前判断x的范围;
我自己一直以为他们的做法是: log_5(x!)这样的做法, 但是这个做法实际上最后会比他们这个直接除法累加的方法慢很多;
那么awice这个解释第二行这个公式: 计算number of times 5 divides x!的方法, 是怎么知道就是可以用这个公式来做的呢?
@wilderfield Imagine an expression for n! = 1 2 3 ... n, zeroes are all produced by multiplying 2s and 5s which are in its factorization, therefore if we count the number of 2s and number of 5s and take the minimum we'll have the number of zeroes at the end. Again, notice that every kth number in n! expression can be divided by k, therefore there are floor(n/k) such numbers. Same is true for n/k^2 and so on until n/k^i > n.
Using that we can count the number of 2s and 5s as it's described in the solution, one small point to notice is that every number that can be divided by 2^i only contributes 1 to the count of 2s as we have counted the other i - 1 contributions in previous steps.
这个人这么一说大概就知道了, 比如x是26, 那么最后zeta(x)就是5 + 1 = 6, 因为从1..26当中, 有5个数字能被5整除, 有1个数字能被25整除; 这样最后26!里面, 实际上就有6个5: 这个公式的意义就是, 第一个算/5的时候, 其实25这个数字, 也是贡献了一个5的, 然后在下一个iteration, 10这样的, 因为只能贡献一个factor 5, 已经被除掉了, 所以就无法贡献了, 但是25这个时候是还剩下一个的, 就还可以贡献多一个;
这个公式的复杂性我一开始看uwi做法的时候还真的是没有理解;
理解了这个, x/5 <= zeta(x) <= x.也就不难理解了;
根据这个观察, 把代码里面的上限改成5K+1实际上也AC了;
awice这个代码几乎就是把这个题目的最优解法表达出来了;
class Solution {
public:
int preimageSizeFZF(int K) {
int sum[13]={1};
for (int i=1; i<13; i++) sum[i]=sum[i-1]*5+1;
for (int i=12; i>=0; i--) {
if (K/sum[i]==5) return 0;
K=K%sum[i];
}
return 5;
}
};
Let g(x)=f(x)-f(x-1), so f(x)=sum{g(x)}.
We can find that
g(x)=0 if x%5!=0,
g(x)>=1 if x%5==0,
g(x)>=2 if x%25==0,
…
List g(x) as follows:
x: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 …
g(x): 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 2 …
x: 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 100 105 110 115 120 125 …
g(x): 1 1 1 1 2 1 1 1 1 2 1 1 1 1 2 1 1 1 1 2 1 1 1 1 3 …
so g(x) will always repeat a sequnce for 5 times and +1 at the last number of the sequence.
Some K is/are skipped if g(x)>1.
For example, when x=25, g(x)=2, K=5 is skipped(there is no x that f(x)=5), and when x=125, g(x)=3, K=29, 30 are skipped.
We can find that 5(=15), 11(=61+5), 17(=62+5), 23(=63+5), 29(=64+5), 30(=65), 36(=31+5), 42(=31+6+5), 48(=31+6*2+5), … are skipped.
Let me know if there are ambiguities.
刚开始没有看懂, 不过后来发现他这里的思路还是挺有意思的: 因为在某些位置, f(x) - f(x-1)会超过1, 所以这个实际上就是导致有一些 f(x)的value被跳过了(因为增长幅度超过了1, sum最后就不连续);
具体的数学的计算没有仔细验证了;
i:(1), sum:(6)
i:(2), sum:(31)
i:(3), sum:(156)
i:(4), sum:(781)
i:(5), sum:(3906)
i:(6), sum:(19531)
i:(7), sum:(97656)
i:(8), sum:(488281)
i:(9), sum:(2441406)
i:(10), sum:(12207031)
i:(11), sum:(61035156)
i:(12), sum:(305175781)
感觉就是观察规律总结出来的一些东西, 看了半天没怎么看懂; 尤其是他最后代码上面的判断, 判断/sum是否等于5, 这个是什么道理? 而且真正面试的时候, 这样一个算法是有点差强人意的, 理论上的分析并不到位, 更多的是依靠的找规律;
- when n>=5, the number of zeros in n! is the count of factors of 5. This function nzero has a complexity of O(log(n)).
- therefore, (5K)! should have more than K zeros, if K >= 1.
- use a binary search in [1, 5K] to find the smallest number n, so that nzero(n) >= K. This has a complexity of O(log(5K)).
- if ‘nzero(n) == K’, the numbers in range [n, n + 5 - n % 5) are all valid candidates. As mentioned by @vikchernij, because the valid n should be always a multiple of 5, the result should be always 5 in this case.
- otherwise, there is no valid numbers.
- the total complexity is O(log(5K) * log(5K)), which is very small.
class Solution:
def preimageSizeFZF(self, K):
def nzero(n):
f = 5
cnt = 0
while f <= n:
cnt += n // f
f *= 5
return cnt
if K == 0:
return 5
min = 1
max = K * 5
while min < max:
mid = (min + max) // 2
if nzero(mid) < K:
min = mid + 1
else:
max = mid
if nzero(min) != K:
return 0
else:
# next = (min // 5 + 1) * 5
# return next - min
return 5
解释的比较一般, 有点牵强附会的嫌疑, 不过算法本身跟之前看到的是一样的;
One way to go about it is the number theory way of computing number of zeros at the end of a factorial: recursively divide the quotient with 5. So there is always at least one extra zero for every 5 number interval.
Read:https://mathoverflow.net/a/16255
这个好像背后还真的是有点说法的;
Given N - No. of zeroes in N! can be found by N/5, N/25, N/125 so on
So Here use Binary search, from 0 to 10^9 - take mid element and check for No. of ZeroesFind lower range and Higher Range : in between that is the numbers
Lower Range : Strictly
=K zeroes No. of zeroes Range once it starts - it will never decrease
Example
0! - 4! - 0 zeroes
5! - 9! - 1 zero
10! onwards 2 zeroes, so on
class Solution {
public int preimageSizeFZF(int K) {
// findRange(K)- All elements factorial <= Kzeroes
// findRange(K-1) -All elements factorial <= K-1 zeroes
return findRange(K)-findRange(K-1);
}
// Using Binary Search
int findRange(int k){
long low = 0, high = Long.MAX_VALUE;
while(low<=high){
long mid = low + (high-low)/2;
if(getZeroes(mid)>k) high = mid-1;
else
low = mid+1;
}
return (int)low-1;
}
// get zeroes in N!
long getZeroes(long N){
long count = 0;
for(long i=5;N/i>=1;i=i*5){
count+=N/i;
}
return count;
}
}
这个就是uwi的解法;
uwi做法:
class Solution {
public int preimageSizeFZF(int K) {
return (int) (count(K) - count(K-1));
}
public long count(int n)
{
long low = -1, high = 5000000000L;
while (high - low > 1){
long h = high + low >> 1;
long s = 0;
for (long k = h/5; k > 0; k /= 5) s += k;
if (s <= n) {
low = h;
} else {
high = h;
}
}
return low+1;
}
}
大概回忆起来这题的做法了, 基本上的核心思想就是有多少个5有多少个trailing 0.
count 3 returns 20
count 2 returns 15
先不看这个结果, 先想想如果是你自己怎么数? 比如K是3, 那么你做法很简单, 从1开始, 然后一个个往后面乘;
光是看这个, 你可能觉得, 好像是不是用DP比较好? 但是这题因为没有overlapping, 所以DP并没有受益, 最后你实际上做的就是一个linear search; 这里也就带出来为什么他们用binary search: 很明显的一个线性排列好的结构, binary search是很自然的;
然后看他这个count的结果, 你看他最后返回之前, 有一个+1, 实际上就是一个上限操作; count返回的应该是比最大的可以拥有n个0的数字再大一个; 一个开区间的上限, 然后两个进行一个减法;
比如还是上面这个图, 你很容易看出来, 我最后K等于3的时候, 结果是5, 这5个数字就是, 15!, 16!, 17!, 18!, 19!; 那么这里大概就能看出来这个count函数的作用了, 对于count(3), 他返回的是20, 就是最大的19, 再多一个; 当然作为这题来讲, count最后这个+1不带上也无所谓; 可能uwi有他自己的理由;
知道这个, 大概就能理解他这个binary search找的是什么: maximum X such that X! has n trailing 0s. 当然这个具体设计也有点讲究, 他们这种大神, 三四分钟就写完了, 真的是没的比, 如果是我写, 调试估计都得调半天;
不知道最后awice会给一个什么样的解法, 不过uwi这个解法现在理解来看, 其实是很聪明的了; 没想到这题他也能用difference, 也就是差值的思路来做. 之前那个LR那题, 差值思路还算明显, 这题居然他也能找到;
回头想想, 如果你把上面那个图片画出来, 实际上还是不难理解, 你最后找的就是这个interval;
Problem Description
Let f(x) be the number of zeroes at the end of x!. (Recall that x! = 1 2 3 ... x, and by convention, 0! = 1.)
For example, f(3) = 0 because 3! = 6 has no zeroes at the end, while f(11) = 2 because 11! = 39916800 has 2 zeroes at the end. Given K, find how many non-negative integers x have the property that f(x) = K.
Example 1:
Input: K = 0
Output: 5
Explanation: 0!, 1!, 2!, 3!, and 4! end with K = 0 zeroes.
Example 2:
Input: K = 5
Output: 0
Explanation: There is no x such that x! ends in K = 5 zeroes.
Note:
- K will be an integer in the range [0, 10^9].
Difficulty:Hard
Total Accepted:170
Total Submissions:756
Contributor:ngoc_lam
Companies
adobe
Related Topics
binary search