### tanishq_code_c's blog

By tanishq_code_c, 3 years ago,

Recently my friend was asked this problem in his coding test

• You are given an array of positive integers and Q queries. Each query if of three types
1) type 1 -> given L and R find product of integers of array whose indices are in range [L, R] modulo 1e9+7
2) type 2 -> find first digit of product of integers of array whose indices are in range [L, R] without modulo 1e9+7
3) type 3 -> update the value of the array at given index.

Example =

arr = [2,3,4,5,6]
L = 1, R = 5

then for type1 = (2 * 3 * 4 * 5 * 6) % mod = 720
and for type2 = (2 * 3 * 4 * 5 * 6) = 7 (which if the first digit (from left) in 720)

Constraints :
1 <= N <= 1e5
1 <= arr[i] <= 1e9
1 <= Q <= 1e5
1 <= L <= R <= 1e5

I am able to handle type1 and type3 queries easily with segment tree. But having no idea how to handle type 2 queries
Before posting this blog i did some research about this and found one useful link

Link : https://www.geeksforgeeks.org/first-digit-in-product-of-an-array-of-numbers/
But above link is giving wrong first digit in some case . Ex = [2, 5, 1, 3] answer should be 3 (first digit of 30) but it is giving 2.

Can anyone help with handling type 2 queries.

Thanks!

P.S -> The test is already over

• +16

 » 3 years ago, # | ← Rev. 2 →   +16 It's because of precision errors.If we print out the exact value of fract_S, we find that it's $2.99999999999999955591\ldots$. So what you can do to counteract this is add a small epsilon value, maybe something like $10^{-6}$, and then round down.
•  » » 3 years ago, # ^ |   0 Thanks a lot Ritwin. It worked after adding epsilon value. Can you please tell me how to chose correct epsilon value (on what factors it depends)
•  » » » 3 years ago, # ^ |   +8 It depends on what type you use, usually with double, because you're adding a lot of doubles (I think), $10^{-6}$ is good, if you were using long doubles, $10^{-9}$ would probably be good.
•  » » » » 3 years ago, # ^ |   0 Ok,Thanks
•  » » 3 years ago, # ^ |   0 But still the first digit should be 3 for [2, 5, 1, 3] right??
•  » » » 3 years ago, # ^ |   0 Yes. $2.99999999999999955591 + 10^{-6} = 3.00000099999999955591$, which rounds down to $3$.
 » 3 years ago, # | ← Rev. 4 →   0 int firstDigit(int arr[], int n) { // code here double S = 0; for (int i = 0; i < n; i++) S = S + log10(arr[i] * 1.0); double fract_S = (S - floor(S)); int ans = pow(10, fract_S); return ans; } This same code passed for me on GFG.
•  » » 3 years ago, # ^ | ← Rev. 2 →   +26 Even if it passes, it really shouldn't. For example, on the input 12 3 3 3 7 11 13 37 73 101 137 9901 99990001 You output 1 (fract_S is 0.00000000000000355271). The correct answer is 9, since\begin{equation*} 3 * 3 * 3 * 7 * 11 * 13 * 37 * 73 * 101 * 137 * 9901 * 99990001 = 999999999999999999999999 \end{equation*}Even long doubles are not enough, then fract_s is 0. You can definitely find much harder tests, so honestly, I think it is impossible to get the correct digit with fixed precision doubles. But the logarithm method does giveeither the correct digit or one next to it.Also note that adding epsilon doesn't work here, since fract_S is larger than it should be. Subtracting a value definitely doesn't work either, as you can just make a test with a large power of 10.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 Yeah even after adding eps this test-case is not working fine. so that means should i assume that this problem can't be solved ?
 » 14 months ago, # |   0 Tho this code is not correct but still it passed all the tc of the oa.#include using namespace std; #define MOD 1000000007 typedef long long int lli; struct Node { lli p; long double slog; lli flog; Node() { ; } Node(lli a,long double b,lli c) { p=a; slog=b; flog=c; } }; lli mul(lli a,lli b) { return (a%MOD * b%MOD)%MOD; } const lli N=1e5+1; Node seg[4*N+10]; void build(lli a[],lli si,lli l,lli h) { if(l==h) { long double slog=log10(a[l]*1.0); lli flog=floor(slog); seg[si]={a[l],slog,flog}; return; } lli mid=(l+h)/2; build(a,2*si+1,l,mid); build(a,2*si+2,mid+1,h); seg[si].p=mul(seg[2*si+1].p,seg[2*si+2].p); seg[si].slog=seg[2*si+1].slog+seg[2*si+2].slog; seg[si].flog=floor(seg[si].slog); } void update(lli si,lli l,lli h,lli idx,lli v) { if(l==h) { long double slog=log10(v*1.0); lli flog=floor(slog); seg[si]={v,slog,flog}; return; } lli mid=(l+h)/2; if(idx<=mid) update(2*si+1,l,mid,idx,v); else update(2*si+2,mid+1,h,idx,v); seg[si].p=mul(seg[2*si+1].p,seg[2*si+2].p); seg[si].slog=seg[2*si+1].slog+seg[2*si+2].slog; seg[si].flog=floor(seg[si].slog); } Node query(lli si,lli ss,lli se,lli qs,lli qe) { if(qs>se || ss>qe) { Node n; n.p=1; n.slog=0; n.flog=0; return n; } if(qs<=ss && se<=qe) return seg[si]; lli mid=(ss+se)/2; Node left=query(2*si+1,ss,mid,qs,qe); Node right=query(2*si+2,mid+1,se,qs,qe); Node n; n.p=mul(left.p,right.p); n.slog=left.slog+right.slog; n.flog=floor(n.slog); return n; } int main() { lli n; cin>>n; lli a[n]; for(lli i=0;i>a[i]; build(a,0,0,n-1); lli q; cin>>q; while(q--) { lli qt,l,r; cin>>qt>>l>>r; if(qt==2) { Node ans=query(0,0,n-1,l-1,r-1); long double fract_S=ans.slog-ans.flog; int d= pow(10, fract_S); cout<