T21 - Editorial


[Contest] T21

Author: Nandishwar Garg






You are given two large numbers m and n. You have to multiply m and n then product is needed to be divided by 3. What will be the remainder after division?


To solve the problem, just go through these 3 steps:

Step 1: The given numbers m and n are needed to be multiplied.

Step 2: The product which you get after multiplying the numbers is needed to be divided by 3.

Step 3: Print the remainder you get.


Author’s solution can be found here

Editorial tag shoud be removed from this post. In my opinion this is not an editorial. Its just a duplicate post repeating question again.

Misleading in the name of editorial.

No soln. No proper explanation. Nothing.

Oh really !!

well i don't know how to multiply 2 numbers......XD:)

I think they are asking for the solution ! under the editorial tag… XD lol Xd :

I guess the concept here is that the program should cope when the numbers are too big to multiply. OR perhaps even hold as numbers. Python mostly laughs at those sort of restrictions, but not all are so blessed.

So: if the numbers are inconveniently large for your environment, it’s still easy to find the amswer with modular arithmetic. We can simplify by a number of stages:

Firstly, if we find the remainder of the two input numbers after division by 3, we can multiply those two results together instead of the original numbers, and the answer will have the same remainder. Much easier.

Why does this work? Well, if our two given numbers are a and b, and they have remainders respectively of c and d, this means that a = 3v + c and b = 3w + d. We don’t need to know what v and w are. Then multiplying we get ab = (3v + c)(3w + d) = 9vw + 3vd + 3wc + cd and since 9vw + 3vd + 3wc is clearly divisible by 3, ab and cd have the same remainders.

Now finding out what c and d are is our second stage of simplification. If you know the divisibility test for 3, you know that you can just add up the digits to find out whether a number is divisible by 3 or not. This works for much the same reason above, plus the fact that the remainder of 10 when divided by 3 is 1. This means that k and 10k have the same remainder on division by 3, and likewise 100k, 1000k, 10000k etc. So every digit in the number, no matter how many powers of ten it has been multiplied by to get to its place value, has the same remainder on division by 3 as just that digit alone. You can check this; 40 has the same remainder as 4, 500 has the same remainder as 5, 2000 has the same remainder as 2, etc.

So you can just sum the digits in each of a and b, find their remainders on division by 3, and that’s your c and d above.

If preferred you can bite off larger digestible pieces to evaluate interim remainders, which still works for the same reason - the larger pieces have the same remainder as the sum of their digits.

A more interesting challenge is to find the same but with remainders after division by 7, assuming that the numbers are inconveniently large. The trick then is to find the right size pieces to bite off, and in the right place. Working with single digits is no longer the right approach.

1 Like

exactly…it is not an editorial anyway …XD :slight_smile:

@vijju123 Please mark this answer as accepted.

Bump so that this comes on front page.