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 (a*x)%b == 0.

Let g = gcd(a,b). Let a1=a/g and b1=b/g.

now the relation becomes (a1

*x*g)%(b1

*g) == 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.

Problem can now be stated as number of x such that (a1

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.