haribhatt34's blog

Can't Understand this Question
By haribhatt34, history, 6 years ago, In English

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

  • Vote: I like it
  • -10
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
6 years ago, # |
← Rev. 10   Vote: I like it 0 Vote: I do not like it

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 a vector<int> C++ object when the maximum value of N is known, and the standard library function lower_bound() can be used to find the answer to each query using binary search.

→ Reply