# Find an Integer point on a line segment with given two ends

• Difficulty Level : Easy
• Last Updated : 06 Sep, 2022

Given two points pointU and pointV in XY-space, we need to find a point which has integer coordinates and lies on a line going through points pointU and pointV. Examples:

```If  pointU = (1, -1 and pointV = (-4, 1)
then equation of line which goes
through these two points is,
2X + 5Y = -3
One point with integer co-ordinate which
satisfies above equation is (6, -3)```

We can see that once we found the equation of line, this problem can be treated as Extended Euclid algorithm problem, where we know A, B, C in AX + BY = C and we want to find out the value of X and Y from the equation. In above Extended Euclid equation, C is gcd of A and B, so after finding out the line equation from given two points if C is not a multiple of gcd(A, B) then we can conclude that there is no possible integer coordinate on the specified line. If C is a multiple of g, then we can scale up the founded X and Y coefficients to satisfy the actual equation, which will be our final answer.

## CPP

 `// C++ program to get Integer point on a line``#include ``using` `namespace` `std;` `// Utility method for extended Euclidean Algorithm``int` `gcdExtended(``int` `a, ``int` `b, ``int` `*x, ``int` `*y)``{``    ``// Base Case``    ``if` `(a == 0)``    ``{``        ``*x = 0;``        ``*y = 1;``        ``return` `b;``    ``}` `    ``int` `x1, y1; ``// To store results of recursive call``    ``int` `gcd = gcdExtended(b%a, a, &x1, &y1);` `    ``// Update x and y using results of recursive``    ``// call``    ``*x = y1 - (b/a) * x1;``    ``*y = x1;` `    ``return` `gcd;``}` `// method prints integer point on a line with two``// points U and V.``void` `printIntegerPoint(``int` `pointU[], ``int` `pointV[])``{``    ``// Getting coefficient of line``    ``int` `A = (pointU[1] - pointV[1]);``    ``int` `B = (pointV[0] - pointU[0]);``    ``int` `C = (pointU[0] * (pointU[1] - pointV[1]) +``            ``pointU[1] * (pointV[0] - pointU[0]));` `    ``int` `x, y; ``// To be assigned a value by gcdExtended()``    ``int` `g = gcdExtended(A, B, &x, &y);` `    ``// if C is not divisible by g, then no solution``    ``// is available``    ``if` `(C % g != 0)``        ``cout << ``"No possible integer point\n"``;` `    ``else` `        ``// scaling up x and y to satisfy actual answer``        ``cout << ``"Integer Point : "` `<< (x * C/g) << ``" "``            ``<< (y * C/g) << endl;``}` `// Driver code to test above methods``int` `main()``{``    ``int` `pointU[] = {1, -1};``    ``int` `pointV[] = {-4, 1};` `    ``printIntegerPoint(pointU, pointV);``    ``return` `0;``}`

## Java

 `// Java program to get Integer point on a line``// Utility method for extended Euclidean Algorithm``class` `GFG {` `  ``public` `static` `int` `x;``  ``public` `static` `int` `y;` `  ``// Function for extended Euclidean Algorithm``  ``static` `int` `gcdExtended(``int` `a, ``int` `b)``  ``{` `    ``// Base Case``    ``if` `(a == ``0``) {``      ``x = ``0``;``      ``y = ``1``;``      ``return` `b;``    ``}` `    ``// To store results of recursive call``    ``int` `gcd = gcdExtended(b % a, a);``    ``int` `x1 = x;``    ``int` `y1 = y;` `    ``// Update x and y using results of recursive``    ``// call``    ``int` `tmp = b / a;``    ``x = y1 - tmp * x1;``    ``y = x1;` `    ``return` `gcd;``  ``}` `  ``// method prints integer point on a line with two``  ``// points U and V.``  ``public` `static` `void` `printIntegerPoint(``int``[] pointU,``                                       ``int``[] pointV)``  ``{``    ``// Getting coefficient of line``    ``int` `A = (pointU[``1``] - pointV[``1``]);``    ``int` `B = (pointV[``0``] - pointU[``0``]);``    ``int` `C = (pointU[``0``] * (pointU[``1``] - pointV[``1``])``             ``+ pointU[``1``] * (pointV[``0``] - pointU[``0``]));` `    ``x = ``0``; ``// To be assigned a value by gcdExtended()``    ``y = ``0``;``    ``int` `g = gcdExtended(A, B);` `    ``// if C is not divisible by g, then no solution``    ``// is available``    ``if` `(C % g != ``0``) {``      ``System.out.print(``"No possible integer point\n"``);``    ``}` `    ``else` `{` `      ``// scaling up x and y to satisfy actual answer``      ``System.out.print(``"Integer Point : "``);``      ``System.out.print((x * C / g));``      ``System.out.print(``" "``);``      ``System.out.print((y * C / g));``      ``System.out.print(``"\n"``);``    ``}``  ``}` `  ``// Driver code to test above methods``  ``public` `static` `void` `main(String[] args)``  ``{``    ``int``[] pointU = { ``1``, -``1` `};``    ``int``[] pointV = { -``4``, ``1` `};` `    ``printIntegerPoint(pointU, pointV);``  ``}``}` `// The code is contributed by phasing17`

## C#

 `using` `System;` `public` `static` `class` `GFG {``    ``// C++ program to get Integer point on a line``    ``// Utility method for extended Euclidean Algorithm``    ``public` `static` `int` `gcdExtended(``int` `a, ``int` `b, ``ref` `int` `x,``                                  ``ref` `int` `y)``    ``{``        ``// Base Case``        ``if` `(a == 0) {``            ``x = 0;``            ``y = 1;``            ``return` `b;``        ``}` `        ``int` `x1 = 0; ``// To store results of recursive call``        ``int` `y1 = 0;``        ``int` `gcd = gcdExtended(b % a, a, ``ref` `x1, ``ref` `y1);` `        ``// Update x and y using results of recursive``        ``// call``        ``x = y1 - (b / a) * x1;``        ``y = x1;` `        ``return` `gcd;``    ``}` `    ``// method prints integer point on a line with two``    ``// points U and V.``    ``public` `static` `void` `printIntegerPoint(``int``[] pointU,``                                         ``int``[] pointV)``    ``{``        ``// Getting coefficient of line``        ``int` `A = (pointU[1] - pointV[1]);``        ``int` `B = (pointV[0] - pointU[0]);``        ``int` `C = (pointU[0] * (pointU[1] - pointV[1])``                 ``+ pointU[1] * (pointV[0] - pointU[0]));` `        ``int` `x``            ``= 0; ``// To be assigned a value by gcdExtended()``        ``int` `y = 0;``        ``int` `g = gcdExtended(A, B, ``ref` `x, ``ref` `y);` `        ``// if C is not divisible by g, then no solution``        ``// is available``        ``if` `(C % g != 0) {``            ``Console.Write(``"No possible integer point\n"``);``        ``}` `        ``else` `{` `            ``// scaling up x and y to satisfy actual answer``            ``Console.Write(``"Integer Point : "``);``            ``Console.Write((x * C / g));``            ``Console.Write(``" "``);``            ``Console.Write((y * C / g));``            ``Console.Write(``"\n"``);``        ``}``    ``}` `    ``// Driver code to test above methods``    ``public` `static` `void` `Main()``    ``{``        ``int``[] pointU = { 1, -1 };``        ``int``[] pointV = { -4, 1 };` `        ``printIntegerPoint(pointU, pointV);``    ``}``}` `// The code is contributed by Aarti_Rathi`

## Javascript

 ``

Output

`Integer Point : 6 -3`

Time complexity: O(logn)
Auxiliary Space: O(logn)

My Personal Notes arrow_drop_up