How to find first digit of product of array elements ?

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

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

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; }

#include<bits/stdc++.h> 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<n;i++) cin>>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<<ans.p<<" "<<d<<endl; } else { l--; update(0,0,n-1,l,r); } } return 0; }

Комментарии (10)

Написать комментарий?

Ritwin

4 года назад, # |

← 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.

→ Ответить

tanishq_code_c

4 года назад, # ^ |

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)

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.

Ok,Thanks

shinigami_500

But still the first digit should be 3 for [2, 5, 1, 3] right??

Yes. $$$2.99999999999999955591 + 10^{-6} = 3.00000099999999955591$$$, which rounds down to $$$3$$$.

← Rev. 4 →

This same code passed for me on GFG.

mango_lassi

+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.

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 ?

aditya_01

2 года назад, # |

Tho this code is not correct but still it passed all the tc of the oa.

Блог пользователя tanishq_code_c