Big Multiplication

[3U5X216C]

Given two very large numbers m and n.He asks all the students to find the remainder of product of two numbers m and n when divided by 3.

Help us to solve this problem.

Input Format:
The first line of the input contains an integer T denoting the number of test cases.

Each of the next T lines contains two space separated numbers m and n.

Output Format:
For each test case, Print remainder on a new line.

Constraints:
1<=T<=100
1<=length of m and n <=100000

Why is this not working guys????

  #include <bits/stdc++.h>
using namespace std;

int main() {
    int t;
    int m, n;
    cin >> t;
    while (t--) {
        cin >> n >> m;
        cout << (n * m) % 3 << endl;
    }
    return 0;
}

[Repeater]

n and m are huge. Up to 100000 digits long.

If (n * m) is bigger than 2147483648 (10 digits long) , your four byte signed int can't hold that number.

You need to come up with a way to do this that isn't just trying to read in the numbers as int values and multiplying them.

[3U5X216C]

It gives WA to long long int also

[jonnin]

....
unless I just failed math..
cout << n%3*m%3 << endl; // not sure if this works in general but it sure seems to work for %3 specifically.

check 17 & 17. should get 1, though the remainders are both 2. ;) (its an operator ordering sploit, but I think its right -- 17%3 = 2, 2*17 = 34, 34%3 = 1 ... and I am pretty sure it works for all positive input up to maxpossibleintsize/2 ).

[Repeater]

1<=length of m and n <=100000

m could be 100000 digits long, as could n.

That's far too large to fit into any primitive C++ type to which the modulus operator applies.

cout << n%3*m%3 << endl; would work for only approximately 0.01% (not one percent - one hundreth of one percent) of possible input values for n or m.

[jonnin]

show me? I goof math up from time to time, but I don't see this one. I ran out every possible multiply up to 1000x1000 and not one failure? It may be wrong, but I wouldn't mind 1 example of it not working.

//prints nothing
int main()
{

int x,y,z;

for(x = 0; x < 1000; x++)
for(y = 0; y < 1000; y++)
{
if((x*y)%3 != x%3*y%3)
cout <<x << " " << y <<" " << x%3 << " " << y%3 << " " << (x*y)%3 << " " << x%3*y%3<< endl;

}

return 0;
}

[icy1]

examine the numbers for divisibility by 3. A number that divides 3 with 0 remainder, I'll call "rem0". Then just examine all cases (there are only 4):

rem0 * anything --> 0. Example: 9 * 138571308 % 3 = 0, since 9 divides 3.
rem1 * rem1 --> 1. Example: 13 * 4 % 3 = 1.
rem1 * rem2 --> 2. Example: 10 * 11 % 3 = 2.
rem2 * rem2 --> 1. Example: 194 * 11 % 3 = 1.


How to check divisibility by 3? Add the digits... ezgame

[Repeater]

Here is the biggest number that an eight byte signed int can hold:

9223372036854775807

That's almost a twenty digit number. The max length of n is 100000 digits.

Here is a one hundred digit number: 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Far, far too big. And that's just one hundred digits. The max length of n is 100000 digits. Let's write out a one hundred thousand digit number:

1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000.... we're going to be here a while.

but I wouldn't mind 1 example of it not working.

Try with

n = 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

and m = 99999999999999999999999999999999996666666666666666666000000000000111111111111111111222222222222222222666666666666633333333333338888888885647836585


Your math is fine. It's just the implementation; int cannot hold a one hundred thousand digit number.

[sc7]

only option I see here is to multiply using strings and then mod using string, but I it will give TLE for sure :/

[tpb]

It's commonly known that a number is divisible by 3 if the sum of its digits is divisible by 3. In fact, the modulus by 3 of the sum of its digits is equal to the modulus by 3 of the original number.

Furthermore, the modulus by 3 of the product of the modulus by 3 of each number gives the modulus by 3 of the original product.

So just add up the digits and take the modulus by 3 of that for both input numbers. Then multiply those and take the modulus by 3 of that.

[jonnin]

I don't have an easy way to do big ints at work. Ill have to take your word for it that the equation fails on that one. I don't suppose anyone has a int64 case that fails it? If those actually fail it, did you do the order of operations the same as the 17*17 example? Granted, you need mod (tricky) & multiply (only by 0, 1, and 2, easy) for huge values which is usually poor performance. I am thinking the add the digits trick may be the right solution for the gigantic ones.

[Repeater]

I don't suppose anyone has a int64 case that fails it?

Same numbers. unsigned int64 max value = 18446744073709551615

As soon as you try to use it to hold values of more than 20 digits (which is 99.98% of the possible input values for n and m), all bets are off.

I don't have an easy way to do big ints at work.

If you switch to using something that works with arbitrary sized integers, all bets are back on. I have no idea if the numbers I picked work or not with big int ; the point is that an int cannot hold the full range of values needed for the naive implementation to work.

[jonnin]

oh, yea I said that. It only works to your max size / 2. I understand the overflow issue, I just wanted to know if I screwed up the math! I am wondering if it has any value combined with the digit summation method. /shrug. Probably not. All it really does is get a lot farther than (N*M)%3. Not useful here.

[icy1]

ruby:

# As per Repeater's example
n = "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"
m = "99999999999999999999999999999999996666666666666666666000000000000111111111111111111222222222222222222666666666666633333333333338888888885647836585"

n_sum = 0
m_sum = 0
n.each_char {|c| n_sum += c.to_i}
m.each_char {|c| m_sum += c.to_i}

nr = n_sum % 3
mr = m_sum % 3
if nr.zero? || mr.zero?
    puts '0'
elsif nr==1 && mr==1 || nr==2 && mr==2
    puts '1'
else
    puts '2'
end

https://repl.it/@icy_1/AttractiveMadeupRam

original sums are 1 and 720, the latter of which divides 3. (i)

0

Change last digit of "m" from a 5 to a 6, we now get the [1,1] case; output is 1. (ii)
Change last digit of "m" from a 5 to a 7, we now get the [1,2] case; output is 2. (iii).
Change last digit of "n" from 0 to 1, and last digit of "m" from 5 to 7, we get [2,2] case; output is 1. (iv)

[Repeater]

As an aside, it's always interesting that these kinds of programming challenges are generally almost nothing to do with programming ability; it's the ability to spot or deduce some clever solution that reduces the time or memory required. In cases like this, if you just don't happen to know any number theory, you're really not going to get the answer from your own head.

We're seeing a lot of these recently around here; problems with a simple ("naive") solution that simply take too long or too much memory (or, as in this case, can't actually handle the input values), and smarter solutions people come to ask about.

Anyone know why the sudden rush? Is it hiring season for new grads or some such, with a lot of these puzzles being presented?

[icy1]

When I was first learning Ruby, I'd come across Project Euler , which had a lot of these kinds of problems. For the most part, I pretty much *had* to find some clever way to solve it, and not only because Ruby ran more than 3 times slower than C (I think at one point with 1.8.x, it was even 5x slower).

I remember one of my fav problems was lexicographic permutations, https://projecteuler.net/problem=24

There was just one input area for the answer, so even if your code ran for two hours, as long as you put in the right answer, you'd solve it, but striving for a couple sec or less was the usual goal. After getting it right, you'd get access to forums where people discussed what they did, and posted code in C, C++, Assembly, J, K, Mathematica, Python, Ruby, even old-fashioned "pencil & paper", etc. Some people 'cheated' by creating giant pre-compiled caches, or simply used built-in Mathematica methods or so, but really they were just cheating themselves.

As for your question about the rush... shrug, it's summer, school's out, and though a lot of these are not quite 'interview' problems, some of them do touch upon traveling salesman, trees, etc. I don't quite remember how to solve suffix tree problems, so if someone could find a good one of those involving alphabetical combinations or so, that'd be cool.

[ghostrideriit]

Store digits in a string take sum of digits....

Think further