Find an Integer point on a line segment with given two ends
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 <bits/stdc++.h> 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
<script> // Javascript program to get Integer point on a line // Function for extended Euclidean Algorithm function gcdExtended(a,b) { // Base Case if (a == 0) { x = 0; y = 1; return b; } // To store results of recursive call let gcd = gcdExtended(b % a, a); let x1 = x; let y1 = y; // Update x and y using results of recursive // call let tmp = Math.floor(b/a); x = y1 - tmp * x1; y = x1; return gcd; } // method prints integer point on a line with two // points U and V. function printIntegerPoint(pointU,pointV) { // Getting coefficient of line let A = (pointU[1] - pointV[1]); let B = (pointV[0] - pointU[0]); let C = (pointU[0] * (pointU[1] - pointV[1]) + pointU[1] * (pointV[0] - pointU[0])); x = 0; // To be assigned a value by gcdExtended() y = 0; let g = gcdExtended(A, B); // if C is not divisible by g, then no solution // is available if (C % g != 0) { document.write( "No possible integer point\n" ); } else { // scaling up x and y to satisfy actual answer document.write( "Integer Point : " ); document.write((x * C / g)); document.write( " " ); document.write((y * C / g)); } } // Driver code to test above methods let x,y; let pointU = [1, -1]; let pointV = [-4, 1]; printIntegerPoint(pointU, pointV); // This Code is contributed by Pushpesh Raj. </script> |
Python3
class GFG: x = None y = None @staticmethod def gcdExtended(a: int , b: int ) - > int : global x, y # Base Case if a = = 0 : x = 0 y = 1 return b # To store results of recursive call gcd = GFG.gcdExtended(b % a, a) x1 = x y1 = y # Update x and y using results of recursive call tmp = b / / a x = y1 - tmp * x1 y = x1 return gcd @staticmethod def printIntegerPoint(pointU, pointV): global x, y # Getting coefficient of line A = (pointU[ 1 ] - pointV[ 1 ]) B = (pointV[ 0 ] - pointU[ 0 ]) C = (pointU[ 0 ] * (pointU[ 1 ] - pointV[ 1 ]) + pointU[ 1 ] * (pointV[ 0 ] - pointU[ 0 ])) x = 0 # To be assigned a value by gcdExtended() y = 0 g = GFG.gcdExtended(A, B) # if C is not divisible by g, then no solution is available if C % g ! = 0 : print ( "No possible integer point" ) else : # scaling up x and y to satisfy actual answer print ( "Integer Point : " , end = "") print ((x * C / / g), end = " " ) print ((y * C / / g)) @staticmethod def main() - > None : pointU = [ 1 , - 1 ] pointV = [ - 4 , 1 ] GFG.printIntegerPoint(pointU, pointV) if __name__ = = "__main__" : GFG.main() |
Integer Point : 6 -3
Time complexity: O(logn)
Auxiliary Space: O(logn)