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
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 (a1*x*g)(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.