## PROBLEM LINKS:

Practice

## Setter : Shubham Grover

## DIFFICULTY:

Easy-Medium

## PREREQUISITES:

Math,Segment Trees,Lazy Propagation

## EXPLANATION:

There are 2 types of queries and seeing the constraints we have to process them faster.

Now,we can use segment trees to answer the queries.We can determine the number of zeroes

at the end of a number if we know number of #twos and #fives in its prime factorization.

Number of zeroes=Min(#twos,#fives).

Number of zeroes in product=Min(sum of #twos in elements in product,sum of #fives in elements in product).

Be careful of element having value 0 in product as number of zeroes will be 1.

Since any array element can have value 0 at any point of time we store 3 values at a node

in segment tree sum of number of twos in prime factorization of all the elements in range,

sum of number of twos in prime factorization of all the elements in range and number of

elements in range with value 0.

Now, using lazy propagation we can answer queries in O(log2(Max A[i])+logN) time;

Total Complexity :O(Nlog2(Max A[i])+Q(log2(Max A[i])+logN))

O(log2(Max A[i])) is for calculating number of twos and fives in prime factorization of number.

## SETTER'S SOLUTION:

Can be found here

asked
**10 Oct '16, 20:44**

2★mightysg

4●1

accept rate:
0%