tanishq_code_c's blog

How to find first digit of product of array elements ?
By tanishq_code_c, 4 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

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

»
4 years ago, # |
← Rev. 2   Vote: I like it +16 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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)

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      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.

      → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
»
4 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

tanishq_code_c 

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +26 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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 ?

      → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Tho this code is not correct but still it passed all the tc of the oa.
→ Reply