Cracking Coding Interview - 16.5 Factorial Zeros

Factorial Zeros: Write an algorithm which computes the number of trailing zeros in n factorial.

Hints: #585, #711, #729, #733, #745

求n的阶乘里，尾部有多少个0。

解法1(不好)

算出n!然后看尾部有多少个0。

1
2
3
4
5
6
7
8
9


public int zeros(int n) {
  int f = fractorial(n);
  int count = 0;
  while (f % 10 == 0) {
    count++;
    f = f / 10;
  }
  return count;
}

这个方法的缺陷在于n的阶乘会很快就变得很大，int类型会溢出。

解法2

如果一个数字尾部出现0，那么就意味着10是它的因子，而10的因子则是2和5。也就是说如果两个数字，一个是2的倍数，一个是5的倍数，那么它们两个相乘就能得到等到一个10，那就会在尾部出现一个0。

因为在1～n的连续数字中，2的倍数的数量总是比5的倍数的数量多，因此只要看5的倍数就行。

而且不光要看这个数是否5的倍数，还要看它的因子里包含了多少个5，比如15的因子是3 * 5，提供了一个5，可以和一个2相乘得到10。25的因子是5 * 5，提供了两个5，可以组成两个10。75的因子是5 * 5 * 3，同样提供了两个5。

比如下面的阶乘：

1

1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * ...

实际上贡献10的数字是：

1

2 * ... * 5 * ... * 10 * ... * 15

所以代码就变成了在[1, n]的范围内，遍历每个数字，看它们的因子里有多少个5，然后累加起来：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


public int countFactor5(int i) {
  int count = 0;
  while (i % 5 == 0) {
    count++;
    i = i / 5;
  }
  return count;
}

public int zeros(int n) {
  int count = 0;
  for (int i = 1; i <= n; i++) {
    count += countFactor5(i);
  }
  return count;
}

解法3

可以比解法2更高效，比如我们可以看[1, n]之间5的倍数有多少个，再看25的倍数有多少个，125的倍数有多少个。

1
2
3
4
5
6
7


public int zeros(int n) {
  int count = 0;
  for (int i = 5; i <= n; i = i * 5) {
    count += n / i;
  }
  return count;
}

Cracking Coding Interview - 16.5 Factorial Zeros

解法1(不好)

解法2

解法3

版权

评论

Cracking Coding Interview - 16.5 Factorial Zeros

解法1(不好)

解法2

解法3

版权

相关文章

评论