I am having trouble understanding this question. Sorry the images are not quite clear, it's a snapshot from the PC. This question was asked previous year by a company which came to our college for recruitment.
The input example given are more like the multiple of 5. But I think there is more the question I am missing.
Thanks
UPDATE Don't know why images are not getting uploaded. Image 1, part 1 Image 1, part 2
Note that F(X) is the power of 5 in the prime number factorization of X.
In the given example, 250 = 21.53 is the prime number factorization of 250. Therefore, F(250) = 3.
If X is not divisible by 5, then F(X) = 0.
Let p be the largest integer such that
.
Then, the answer to the query N is 5p.
S(p) can be computed iteratively as
S(p) = S(p - 1) + F(5p), where p ≥ 1, and the base case is S(0) = 0.
Finally, the sequence S(0), S(1), S(2), ... is strictly increasing, as it is guaranteed that F(5p) ≥ 1. Therefore, the sequence can be stored in an
int
array or avector<int>
C++ object when the maximum value of N is known, and the standard library functionlower_bound()
can be used to find the answer to each query using binary search.Thanks a lot man, for the explanation.
With pleasure