tanishq_code_c's blog

By tanishq_code_c, 3 years ago, In English

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

Full text and comments »

  • Vote: I like it
  • +16
  • Vote: I do not like it