# KDATZERO - Editorial (Kodeathon 15.2)

Practice

Contest

Author: Satyam Gupta

Tester: Pulkit Sharma

Editorialists: Satyam Gupta

MEDIUM

### PREREQUISITES:

Segment Tree with Lazy Propagation, Number Theory

### PROBLEM:

You are given N integers, denoted by A_1, A_2, … , A_N
Now you are given Q queries, each of whom is of following two types:
Type 1: 1 L R: Print the no. of trailing zeros (zeros in the end) in the multiplication of no.s in range [L,R] of array A[], i.e. no. of zeros in A_L * A_{L+1} * … * A_R
Type 2: 2 L R V: Multiply the all the numbers in range [L,R] with V.

### EXPLANATION:

A number has trailing zeros equal to the no. of times it can be divided by 10 with remainder 0. Since 10 = 2*5, in other words we can say that a number has trailing zeros equal to the no. of times it can be divided by both 2 and 5 with remainder 0. So, we don’t need the number itself rather the no. of times it can be divided by 2 and 5 with remainder 0. So, if a number can be divided by ‘2’ for x times and by ‘5’ for y times, then that no. will have min(x,y) trailing zeros.
Since any element of array can go only upto 2000, we can calculate the no. of times a number can be divided by 2 and 5 for all numbers from 1 to 2000 using this pseudo-code:

`````` for i=1 to 2000:
div2[i]=0
div5[i]=0
x=i
while x%2==0 :
div2[i]=div2[i]+1
x=x/2

while x%5==0 :
div5[i]=div5[i]+1
x=x/5
``````

In other words div2[i] = no. of times 2 appear in prime factorization of i and similarly div5[i] = no. of times 5 appear in prime factorization of i

Now for example,
1500 = 2*2*3*5*5*5
So, div2[1500]=2 and div5[1500]=3
then, no. of trailing zeros in 1500 = min(2,3) = 2

Then for no. of trailing zeros in the multiplication of no.s in range [L,R],
x=div2[A_L]+div2[A_{L+1}]+...+div2[A_R]
y=div5[A_L]+div5[A_{L+1}]+...+div5[A_R]
No. of trailing zeros = min(x,y)

Since we need to work on ranges, we can use segment tree. For each node that represents range [L,R] we need to keep sum of the div2 and div5 from A_L to A_R.
For merging left and right nodes into the parent node, refer to the pseudo-code below:

`````` merge(parent,left,right):
parent.two = left.two + right.two
parent.five = left.five + right.five
``````

Because update queries over ranges, we need to use lazy propagation on segment tree.
For type 2 queries of form (2 L R V), we will store the changes to be made (i.e. adding div2[V] and div5[V] to the node members “two” and “five” respectively of range [L,R]) seperately and then later during the Type 1 query, update the tree as needed.

Complexity of this solution:

For preprocessing O(NlogN) and for each query O(logN)

Final complexity = O(NlogN + QlogN)

### AUTHOR’S AND TESTER’S SOLUTIONS:

``````#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>

using namespace std;

#define N 100000
#define MAX 500000

struct Tree_Node
{

int two,five;

} tree[MAX],lazy[MAX],arr[N],dummy;

int div2[2005],div5[2005];

void build(int node, int a, int b)
{
if(a > b) return;

lazy[node].two=lazy[node].five=0;

// Init Values
if(a == b)
{
tree[node].two = arr[a].two;
tree[node].five = arr[a].five;
//cout<<a<<" "<<b<<"node:"<<node<<endl;
return;
}

int lt=node<<1;
int rt=lt+1;

build(lt, a, (a+b)/2);
build(rt, 1 + ((a+b)/2), b);

//Init Internal nodes
tree[node].two = tree[lt].two + tree[rt].two;
tree[node].five = tree[lt].five + tree[rt].five;
}

void update(int node, int a, int b, int i, int j, Tree_Node val)
{

int lt=node<<1; //left child = node*2
int rt=lt+1;    //right child = node*2 + 1

if(lazy[node].two != 0 || lazy[node].five != 0)
{
tree[node].two += lazy[node].two * (b-a+1);
tree[node].five += lazy[node].five * (b-a+1);

if(a != b)
{
lazy[lt].two += lazy[node].two;
lazy[lt].five += lazy[node].five;
lazy[rt].two += lazy[node].two;
lazy[rt].five += lazy[node].five;
}

lazy[node].two = lazy[node].five = 0;
}

if(a > b || a > j || b < i)
return;

if(a >= i && b <= j)
{
tree[node].two += val.two * (b-a+1);
tree[node].five += val.five * (b-a+1);

if(a != b)
{
lazy[lt].two += val.two;
lazy[lt].five += val.five;
lazy[rt].two += val.two;
lazy[rt].five += val.five;
}

return;
}

update(lt, a, (a+b)/2, i, j, val);
update(rt, 1+(a+b)/2, b, i, j, val);

tree[node].two = tree[lt].two + tree[rt].two;
tree[node].five = tree[lt].five + tree[rt].five;
}

Tree_Node query(int node, int a, int b, int i, int j)
{
int lt=node<<1;
int rt=lt+1;

if(a > b || a > j || b < i) return dummy;

if(lazy[node].two != 0 || lazy[node].five != 0)
{
tree[node].two += lazy[node].two * (b-a+1);
tree[node].five += lazy[node].five * (b-a+1);

if(a != b)
{
lazy[lt].two += lazy[node].two;
lazy[lt].five += lazy[node].five;
lazy[rt].two += lazy[node].two;
lazy[rt].five += lazy[node].five;
}

lazy[node].two = lazy[node].five = 0;
}

if(a >= i && b <= j)
return tree[node];

Tree_Node q1 = query(lt, a, (a+b)/2, i, j);
Tree_Node q2 = query(rt, 1+(a+b)/2, b, i, j);

if(q1.two==dummy.two) return q2;
if(q2.two==dummy.two) return q1;

Tree_Node res;
res.two = q1.two + q2.two;
res.five = q1.five + q2.five;

return res;
}

int main()
{

//freopen("zeros.in","r",stdin);
//freopen("zeros.out","w",stdout);

int i,n,q,x,l,r,c,t;
Tree_Node val,ans;

dummy.two=-1;

//Calculating the count of 2 and 5 in prime factorization of a no. for no.s upto 2000
for(i=2; i<=2000; i++)
{
x=i;
while(x%5==0)
{
div5[i]++;
x/=5;
}
while(!(x&1))
{
div2[i]++;
x/=2;
}

}
cin.sync_with_stdio(false);
cin.tie(NULL);
//scanf("%ld",&t);
cin>>t;

while(t--)
{
//scanf("%ld%ld",&n,&q); //Input n and q
cin>>n>>q;

for(i=0; i<n; i++)
{
//scanf("%ld",&x); // Input a[i]
cin>>x;

//Only the count of 2 and 5 in it's prime factorization is needed
arr[i].two=div2[x];
arr[i].five=div5[x];
}

build(1, 0, n-1); //Build segment tree

for(i=0; i<q; i++)
{
//scanf("%ld%ld%ld",&c,&l,&r);
cin>>c>>l>>r;

l--;  //Decrease by 1 since array is 0-indexed
r--;

if(c==1)
{
ans=query(1, 0, n-1, l, r); //Query range [l, r] for total no. of twos and fives
printf("%ld\n",min(ans.two,ans.five));
}
else
{
//scanf("%ld",&x);
cin>>x;

val.two=div2[x];   //Only the count of 2 and 5 in it's prime factorization is needed
val.five=div5[x];

update(1, 0, n-1, l, r, val); // Increment range [l, r] by twos and fives of 'val'

}
}
}
return 0;
}
``````
1 Like