snorkel's blog

By snorkel, history, 4 years ago, In English

Trying to solve this problem. I got the last non-zero digit by working with $$$2$$$-s and $$$5$$$-s, but here's an easier solution by using $$$10$$$ directly.

Can anyone explain why this works? How taking modulo $$$10^9$$$ does not make it wrong?

Code

Thanks.

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

»
4 years ago, # |
  Vote: I like it -26 Vote: I do not like it

we're interested in the last digit so even taking modulo $$$10$$$ is right

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

    But it gets wrong answer.

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

    Taking modulo 10 actually does not work.

    For example, take 125*8, and you will get 1000, with a last non-zero digit of 1. But what if it was actually 125*18, which is equal to 2250, with a last non-zero digit of 5?

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think it's modulo 1e9 because the zeros will never go past that far on a single iteration, for example instead it could be 1000 if N went up to 99 because the most the zeros will go up at once is twice because of 25 (4*25 = 100).

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

    boocoo What I don't understand is when we do modulo, we lose some information about the number.

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

      It is true that by doing modulo, we lose some information about the actual number. However, we are more interested in the least significant digit (rightmost non zero digit). Taking modulo removes part of the most significant digits (leftmost digits are lost).

      Here, the only purpose of having modulo 1e9 is to keep the answer in such a range that multiplying a big number like N ( <= 2e7 according to the question ), the product still fits in a long long variable.

      By repeatedly dividing ans by 10 inside the while loop, we are losing information about the least significant digits, only if these digits are 0 (ans % 10 == 0). In the same way, we don't need to keep track of unnecessary most significant digits. Doing so, we are focussed on the requirement, i.e., the last (rightmost) non zero digit.

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

        I want to know exactly the reason for that, you haven't told how is it enough.

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

          Let's say at some point you have ans = 123 (after removing the right hand side 0s).

          • Now you multiply ans with some big number 49834344.
          • ans becomes 6,129,624,312.
          • The next number you would be multiplying is 49834343
          • ans would become 305,465,800,425,347,016.
          • On going one step further, you will easily move beyond the range of long long.

          Instead, when you do modulo 1e9 at each step, it will look something like this

          • After multiplying 49834344, ans = 129,624,312 ( modulo 1e9 )
          • Multiply this again 49834343, ans = 6,459,742,425,347,016 = 425,347,016 ( modulo 1e9 ).

          Notice that doing the modulus operation doesn't change the last digits, It only gets rid of the digits to the left. With modulo and without modulo, in both cases the last digits are the same since the modulus is done with a power of 10.

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

            But why it does not work on $$$10^5$$$?

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

              Because you have N <= 2e7. If you take any modulo lesser than that, it will cause the multiplying value to be truncated. The nearest power of 10 above that value of N is 1e8. That might work.

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

                Ok, thanks. But I'm still little bit confused.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Maybe you need to calculate factorial[n] * inverse(factorial[m])?

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

    Modulo 10 inverses should not work, it is composite.

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

      oh yes, didn't notice that

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

      what is the range of n and m?

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

        both at most 20000000

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
          Rev. 3   Vote: I like it 0 Vote: I do not like it

          I think the reason they choose the mod depends on the range of n and m, since the maximum is 20000000, the product after each steps always has no more than 8 trailing zeroes, so we need a number that larger than 10^8. Besides if we choose 10^10, the product each steps can be larger than 2^64-1, which leads to error. That's my opinion :)

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

            But I first remove those 0-s and then take the mod, not before.

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

              Take a minor example, 3125 mod 10^3 = 125, 3125 mod 10^2 = 25, multiply both by 4 and we get 500 and 100, after moving the zeroes we get two different solutions, so we need a large number to decrease this probability As I mentioned in the last comment, 10^9 is good enough since 10^10 is risky :)

»
4 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Any better explanations are still welcome.

»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

It doesn't work for $$$5^{10}=9765625$$$ as far as I understand

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

    What do you mean does not work? There are two values in the problem $$$n$$$ and $$$m$$$.

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

      I meant n=5^10, m=n so you are calculating factorial, basically

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

        It seems like it's correct.

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

          actually I bugged in my reimplementation, it's $$$n=m=5^{10}+1$$$, it prints 8 instead of 4

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

            Ok, the interesting thing is how did u find it.

            • »
              »
              »
              »
              »
              »
              »
              4 years ago, # ^ |
              Rev. 3   Vote: I like it 0 Vote: I do not like it

              well, it's clear that the problem is with 2's and 5's , because without them (I mean if 10 wouldn't have divisors) everything would work, but not with 10's (because zeros will be handler OK automatically). So, tried nearby $$$5^{10}$$$

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 3   Vote: I like it +20 Vote: I do not like it

      $$$n=5^{10}+1$$$

      $$$m=11$$$

      The correct answer is 8, but the program outputs 6.

      There is actually a smaller counterexample:

      $$$n=5^9+13$$$

      $$$m=14$$$

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

        Thanks for the correct counterexamples. I also checked on my another code (with 2-s and 5-s) and the correct answer is 8 indeed.

        But the question is, how did you find it?

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

          I compared the correct answer(using $$$mod=10^{18}$$$ and __int128) and the answer given by the code written in the blog on values of n close to a power of 5 and small values of m.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I was convinced this was true and was trying to prove it, but got stuck in some part of the proof. I'll leave my attempt with a mark in the error.

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

    The solution only works for $$$n<5^9$$$, so proving that it works for $$$n<10^9$$$ is impossible.