×

# COUNZ - Editorial

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

2★mightysg
41
accept rate: 0%

19.5k348496535

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,038
×1,654
×816
×155
×41
×1

question asked: 10 Oct '16, 20:44

question was seen: 693 times

last updated: 02 Jan '17, 15:22