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.
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)
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.
P.S -> The test is already over