# Trailing Zeros in Factorial | InterviewBit | LeetCode | Solution Explained

I explain the solution to the problem Trailing Zeros in Factorial using simple observations and logic. Problem Link.

## 0. Trailing Zeros in Factorial: Problem Discussion

### 0.0. IO Format

- input:
- an integer, n

- output:
- an integer, which is the number of zeros in n!

- constraints:
- 1 <= n <= 10
^{4}

- 1 <= n <= 10

### 0.1. Examples

- n = 2 -> 2! = 4 -> 0 trailing zeros
- n = 5 -> 5! = 120 -> 1 trailing zero
- and so on.

## 1. Trailing Zeros in Factorial: First Thoughts

The first instinct is to do as the question says. We know how to calculate factorial of a number in O(N) time and space each, so this solution shouldn’t be too hard?

There is one issue though. When it comes to factorials, the number grows fast. Even faster than exponentials – which is saying something. This means that by the time we reach 10^{4}, we would have too many zeros. Yes, even for python3.

This means that we need to find an approach that does not calculate factorials, but just the number of zeros in a factorial.

## 2. Trailing Zeros in Factorial: Observations & Logic

### 2.0. Intuitions

The first thing to notice is that 10! does not have 1 zero for one 10 that is obviously present.

10! is 10.9.8….5….2.1.

Notice something? There’s a 5 and 2 also present, making the answer for 10 2, since we have one zero for 10 and the other for 5*2. The question itself hints at this with the 5! example, giving us 1 as the answer.

### 2.1. 5s and 2s

Now that we know we can form zeros with 5s and 2s, the next question is how many 5s and 2s can we get, apart from 10s?

In 20!, we have 10 and 20, but also 2,4,6,8,12,14,16,18 (we can extract at least one two from each) and then 5,15 (we can extract at least 1 five from each).

One thing that is very evident is that the number of 5s we can extract is much lower than the number of 2s that we can extract. In other words, 5 forms a bottleneck, so we can just count the number of multiples of 5s to get the answer!

Note how 20/5 = 4, which also happens to be the actual answer for n = 20!

### 2.2. Hidden in Plain Sight

It may seem tempting to assume `n // 5`

is the final answer. However, we haven’t really considered the cases where there can be multiple 5s hidden inside the number. Take for example, n = 30.

Online calculator can show that the number of 0s in 30 is 7. However, our logic will print 30/5 = 6. Where in the world did the extra 1 come from?

The big point is that there is a number, 25, in the 30! numbers list that contributes 2 to the final result – it has 2 multiples of 5 hidden inside of it.

This means that we:

- only care about multiples of 5
- of those multiples, we see how many 5s we can extract

And this brings us to the implementation.

## 3. Trailing Zeros in Factorial: Optimized Implementation

### 3.0. Code

int Solution::trailingZeroes(int A) { int count = 0; for (int i = 0; i < A+1; i += 5) { int x = i; while ((x % 5 == 0) && (x > 0)) { x /= 5; count++; } } return count; }

class Solution: def trailingZeroes(self, A): count = 0 for i in range(0, A+1, 5): while i % 5 == 0 and i: i //= 5 count += 1 return count

### 3.1. Complexity Analysis

- Time:
`O(N)`

, to iterate over all the N values from 1 to 10^4. Note that O(N/5) = O(N) - Space:
`O(1)`

, since we do not store anything more than some counters.

### Recommended Posts

##### Gas Station | InterviewBit | Solution Explained

June 13, 2022

##### Majority Element | InterviewBit | Solution Explained

June 13, 2022

Please write the proof.

This solution need an amendment for 2 digit number.

Please write a Proof for this

Matt Michael D’Agati is the founder of Renewables Worldwide, an Solar Firm in MA.

A few age ago, taking a leap of faith, Matt D’Agati delved into the realm of solar, and/or in a short occasion commenced effectively marketing significant amounts of power, primarily around the business industry, collaborating with solar farm developers and local businesses in the “design” of their unique plans.

Ongoing marketing within the sector, offered Matthew to participate a regional startup two years in the, and in a short time, he assumed the role of their Chief Strategy Officer, in charge of all operation and endeavor improvement, in addition to being marketed social group property.

To planned unions and shear get the job done mentality, Matthew D’Agati brought that firm from an initial initial-year revenue to in excess of a 2 hundred% surge in overall money by yr two. Based on that foundation, RW, a experienced-operated company, was produced with goal of giving you alternative electrical remedies for a more intelligent and more sustainable future.

Even more mainly, recognizing there is an untapped market in the market place and an improved approach to realize final results, RW is one of a handful of manufactures in the u.s. to place emphasis on individual acquire, concentrating in both industrial and home solar-powered town off-take. Its visualization is to make a purchases commercial infrastructure on a community-based, statewide, countrywide level, offering various sustainable fuel goods within the of RW.

This enthusiasm in the actual sustainable industry goes on to stimulate and inspire Matthew in enduring his solicit to work with institutions that have the unchanging of offering limitless fuel tips for a a whole lot more ecological destiny. Matt has already a new in companies from Hesser College.

Understanding why solar energy consultants assist clients via Matthew D’Agati.

Sustainable Energy and Electricity Poverty: Bridging the Imbalance by matt d’agatiMatt D’Agati e3d74c8