You are not logged in. Please login at www.codechef.com to post your questions!

×

COUNZ - Editorial

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

mightysg's gravatar image

2★mightysg
41
accept rate: 0%

edited 02 Jan '17, 15:22

admin's gravatar image

0★admin ♦♦
19.6k349497539

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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,198
×1,703
×864
×156
×42
×1

question asked: 10 Oct '16, 20:44

question was seen: 715 times

last updated: 02 Jan '17, 15:22