10407  Simple division
Moderator: Board moderators
Re: 10407  Simple division
I see that you already got accepted.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

 New poster
 Posts: 49
 Joined: Mon Jun 16, 2014 7:40 pm
Re: 10407  Simple division
Yes, by the method of gcd. But i couldn't understand the test case. Will someone plz throw some light on the 3rd test case??
Re: 10407  Simple division
There is mistake in mod calculation. (22) % 3 = (21) % 3 + (1) % 3 = 0 + (1 + 3) % 3 = 2.14%3 = 2
whereas 22%3 = 1
Or (22) % 3 = (22 + 3 + 3 + 3 + 3 + 3 + 3 + 3 + 3) % 3 = 2.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

 New poster
 Posts: 49
 Joined: Mon Jun 16, 2014 7:40 pm
Re: 10407 Simple Division  Can anybody explain!?
Let there be 3 (replace "3" with "n" after I complete the explanation) numbers, n1, n2, n3.theylosehope wrote:Hello guys,
I've got "10407  Simple Division" AC using the description in Algorithmist. However, I don't fully understand it.
My algorithm:
 Add numbers to set "S".
 If size of S is two: print the difference between the two numbers.
 If size of S is > 2: Erase the first element, and find GCD among all the differences between the remaining numbers.
This works correctly. But can anybody explain it in simple words? How can I figure out that the largest dividend with same remainder among a set of numbers is the GCD among the differences except the first difference?
Thanks in advance.
The problem claims that there exists a number, "x" which given same remainder, "r" when you divide each of the three numbers with x.
I know for a fact that, if one removes the remainder from a dividend, then the number so obtained becomes completely divisible by divisor( "x" in this case) (which I still have to find). Taking this further, if I subtract "r" from each number like  "n1r", "n2r", and "n3r", then these numbers would be divisible by x.
So we have a number "x" which divides 3 numbers (GCD is screaming!!!). Yes!! x = GCD( n1r, n2r, n3r) is your answer. So if you generate "r" iteratively (like r = 0, 1, 2, ...) and subtract it from each number and then find the GCD then, BAM!! You have your answer!
(The above solution is likely to TLE, but it is important to understand the "improved" solution)
Let's try to improve this further 
My goal is to reduce each number in the list to a values that give me remainder 0. More precisely, I want to convert >
n1 > n1r
n2 > n2r and
n3 > n3r. But in just one step!. How? How?
If I make the first number (n1) as 0, and subtract n1 from each of the other number then I have something like this 
n1 = 0
n2 = n2  n1
n3 = n3  n1
If I choose any number as a divisor and n1 as the dividend, then the remainder is always going to be zero. So in order to find a number that divides n2, and n3 completely, I need to find the GCD(n2, n3).