-
-
Notifications
You must be signed in to change notification settings - Fork 31
Expand file tree
/
Copy pathTrailing Zeros.java
More file actions
executable file
·100 lines (85 loc) · 2.34 KB
/
Copy pathTrailing Zeros.java
File metadata and controls
executable file
·100 lines (85 loc) · 2.34 KB
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
E
tags: Math
```
/*
LintCode
Write an algorithm which computes the number of trailing zeros in n factorial.
Example
11! = 39916800, so the out should be 2
Challenge
O(log N) time
Tags Expand
Mathematics
Thoughts:
Attempt1:
Can this problem be converted to : how many 10's to I have?
Loop through n, and check how many 2s, 5s do we have.
For each i, do while loop and count the number of 2s, and 5s in that particular i.
Note:
5 and 2 makes 10. So don't worry about 10.
Some values will be checked redundantly, so record the ones checked, return the hash value directly.
Attempt2:
Don't even need to worry about 2's because 2 is definitely more than 5's. Only need to care about 5's.
How many 5's? n/5. loop (1 ~ n)
However, some number within (1 ~ n) may give more 5's, which for example is: 25 = 5 * 5, double 5's. And 125 = triple 5's.
In fact count = n / 5 + n / 25 + n / 125 + ....
*/
class Solution {
/*
* param n: As desciption
* return: An integer, denote the number of trailing zeros in n!
*/
public long trailingZeros(long n) {
if ( n < 5) {
return 0;
}
long count = 0;
for (long i = 5; n / i != 0; i *= 5) {
count += n / i;
}
return count;
}
}
/*
//Attempt 1:
//This solution exceed time limit, and it's over-complex. 滚粗。
class Solution {
private HashMap<Long, Long> mapTwo = new HashMap<Long, Long>();
private HashMap<Long, Long> mapFive = new HashMap<Long, Long>();
public long trailingZeros(long n) {
if (n < 5) {
return 0;
}
long countFive = 0;
long countTwo = 0;
for (int i = 1; i <= n; i++) {
if (i % 2 == 0) {
countTwo += countExistance(i, 2, mapTwo);
}
if (i % 5 == 0) {
countFive += countExistance(i, 5,mapFive);
}
}
return (countFive < countTwo) ? countFive : countTwo;
}
public long countExistance(long n, long m, HashMap<Long, Long> map) {
long temp = n;
long count = 0;
double num = (double)n;
while (num / m == n / m) {
count++;
n = n / m;
num = (double)n;
if (map.containsKey(n)) {
count += map.get(n);
break;
}
}
if (!map.containsKey(temp)) {
map.put(temp, count);
}
return count;
}
};
*/
```