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

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.Thanks a lot Genius3435. 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

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

tanishq_code_c

This same code passed for me on GFG.

Even if it passes, it really shouldn't. For example, on the input

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 ?