Please help me find out solution of the problem on HackerRank Flash and the Lines. How could gcd(abs(x1 -x2 ),abs(y1 - y2)) - 1 be the answer.
i also looking for this ??? need anyone for help
This CF comment gives you nice explanation why is it true.
Lets say the points are (x1,y1) and (x2,y2). Shift the points so that (x1,y1) lies at origin.
New points: (0,0) and (x2-x1,y2-y1)
Line joining these two points of form y=mx+c, where m = (y2-y1)/(x2-x1) and c=0
say x is integer, for y to be integer: ((y2-y1)x)%(x2-x1) == 0
take abs(y2-y1) = a, and abs(x2-x1) = b. So now required condition is (ax)%b == 0.
Let g = gcd(a,b). Let a1=a/g and b1=b/g.
now the relation becomes (a1xg)%(b1g) == 0 where a1 & b1 are co-prime.
Problem can now be stated as number of x such that (a1x)%b1 == 0 where a1,b1 and x are defined above.
Lets say range of x is [0,R] where R = abs(x2-x1), 0 and R inclusive
Number of x would be multiples of b1 in range of x. This is because a1 and b1 have no common factors other than 1, so for the modulo to become 0 there should be a multiple of b1 in numerator.
So number of multiples would be floor(R/b1) + 1.(Extra 1 is for 0).Now subtract the two end points and ans becomes floor(R/b1) - 1. Substitute the values and it becomes floor(abs(x2-x1)/(b/g)) - 1 and b is abs(x2-x1).
After cancelling from numerator and denominator ans is floor(g) - 1 or g-1. Putting value of g ans becomes gcd(y2-y1,x2-x1) - 1.