Count leading zeros of a number
Naive approach
A naive consists on checking if the number is a multiple of 10 or not. If so, divide (integer division) the number by 10 and repeat the process, counting how many times the number is divisible by 10. The algorithm has time complexity of \(O(n)\) where \(n\) is the number of digits of the number and memory complexity of \(O(1)\). For example, \(12300\) is divisible by 10, \(1230\) is also divisible by 10 and \(123\) is not. So, the number leading zeros in \(12300\) is \(2\).
Count leading zeros of a number using its 2's and 5's factors
As \(10=2\times5\), we can re-write above count_zeros function as following:
The code didn't change, but it is easier to see that counting 10 factors is the same as counting pairs of 2 and 5 factors. With that, we could write a new version but slower of the algorithm: