Ruby幼幼班--Factorial Trailing Zeroes

9月快到了,要开始准备一些资料,凑30天用,所以除非有一篇Rails幼幼班的资料,不然不会单独分享解题了。
不是因为K-pop的MV不够用了

Factorial Trailing Zeroes

题目连结:https://leetcode.com/problems/factorial-trailing-zeroes/
题目重点:降幂,"!"号是啥。

5! = 5*4*3*2*1 = 120

题目整理

# @param {Integer} n
# @return {Integer}
def trailing_zeroes(n)

end

p trailing_zeroes(3)  #=>0
p trailing_zeroes(5)  #=>1
p trailing_zeroes(0)  #=>0

如果不清楚对数,我们先看以下资讯

2.7.3 :001 > 5*4*3*2*1
 => 120 
2.7.3 :002 > 3*2*1
 => 6 

乘号按到烦了
写个程序吧

2.7.3 :007 > (1..5).to_a.reduce(:*)
 => 120 
2.7.3 :008 > (1..10).to_a.reduce(:*)
 => 3628800 
2.7.3 :009 > (1..15).to_a.reduce(:*)
 => 1307674368000 
2.7.3 :010 > (1..20).to_a.reduce(:*)
 => 2432902008176640000 
2.7.3 :011 > (1..25).to_a.reduce(:*)
 => 15511210043330985984000000 
 
#自己找出:*是啥,这件事对菜鸟而言,真的很重要。

如果,想直接运用reduce算出结果,然後由後往前算有几个零,这样解是没有错的,但是leetcode上会告诉你,太浪费时间了,直接喷错。

我没有试过,真的!

先找出为何结果会有0

[1, 2, 3, 4, 5] = 120 , 2 * 5 出现 10. 
#代表算式中如果有一组2与5,就会有一个0

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] = 3628800 
#最後一个数字10 = 2 * 5, 两组[2, 5]了, 两个零

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15] = 1307674368000 
#15有一个5,一堆偶数有2,凑三组[2, 5]了,三个零。
#另外发现一件事,2数量一定超过5的数量。

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20] = 2432902008176640000
#20,第四组[2, 5],所以其实我们要找出5的数量,就会有几个零。

[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] = 15511210043330985984000000 
#6个零,因为25 = 5 * 5,25是特别数,有两个5。 4 + 2 = 6

接着我们看一下怎麽找出几个5

#5,10,15,20都比较单纯。直接除即可
2.7.3 :019 > 5/5
 => 1 
2.7.3 :020 > 10/5
 => 2 
2.7.3 :021 > 15/5
 => 3 
2.7.3 :022 > 20/5
 => 4 
 
#25
2.7.3 :023 > 25/5
 => 5
#商数为大於等於5时,需在除一次
2.7.3 :024 > 5/5
 => 1 
#5 + 1 = 6

所以

 5的次数 += n/5
 n /= 5

不放心我们再用菜鸟方法,请电脑告诉我们是否正确

2.7.3 :025 > (1..45).to_a.reduce(:*)
 => 119622220865480194561963161495657715064383733760000000000 
#10个零
2.7.3 :026 > 45/5
 => 9 
2.7.3 :027 > 8/5
 => 1 
#9+1 = 10

2.7.3 :030 > (1..75).to_a.reduce(:*)
 => 24809140811395398091946477116594033660926243886570122837795894512655842677572867409443815424000000000000000000 
#眼睛快花了...18个零
2.7.3 :031 > 75/5
 => 15 
2.7.3 :032 > 15/5
 => 3 

跑回圈吧!

跑n/5的回圈,不是n!的迭代!

def trailing_zeroes(n)
  five_count = 0
  while n > 0
    five_count += n/5
    n /= 5
  end
  five_count
end

#由於如果(小於5的数/5)商数是0,所以不用写额外判断n是否为0的编码了。

大神的one line

def trailing_zeroes(n)
  n == 0 ? 0 : n/5 + trailing_zeroes(n/5)
  #or
  n > 0 ? n/5 + trailing_zeroes(n/5) :0
end
  
#翻成中文不一样,逻辑结果一样...

语法补充

2.7.3 :033 > 10.zero?
 => false 
2.7.3 :034 > 0.zero?
 => true 
2.7.3 :036 > (15/5).zero?
 => false 
2.7.3 :037 > (3/5).zero?
 => true 
 
(n/5).zero? ? 0 : n/5 + trailing_zeroes(n/5)
#其实这写法比较好理解