# Check if two coordinates can be made equal by incrementing/decrementing by K1 and K2 respectively

Given two integer coordinates** (X1, Y1)** and **(X2, Y2)** and two positive integers **K1** and **K2**, the task is to check if both the coordinates can be made equal by performing the following steps any number of times:

- Add or subtract
**K1**from either or both coordinates of**(X1, Y1)**. - Add or subtract
**K2**from either or both coordinates of**(X2, Y2)**.

If it is possible to make **(X1, Y1)** and **(X2, Y2)** equal, then print **Yes**. Otherwise, print **No**.

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

**Examples:**

Input:X1 = 10, Y1 = 10, X2 = 18, Y2 = 13, K1 = 3, K2 = 4Output:YesExplanation:

Following are the moves that can be taken to make both the coordinates equal:

- Move point (X1, Y1) as
(10, 10) -> (10, 13).- Move point (X2, Y2) as (18, 13) -> (14, 13) -> (10, 13)
From the above operations, both the coordinates can be made equal, then print Yes.

Input:X1 = 10, Y1 = 10, X2 = 18, Y2 = 13, K1 = 10, K2 = 10Output:No

**Approach: **This problem can be solved using **Greedy Approach** based on the observation that the moves can be taken in x-direction for **(X1, Y1)** point is **n1 **and the moves taken in x-direction for** (X2, Y2)** point is** n2**, then the expression can be written as:

n1*K1 + n2*K2 = abs(X1 – X2),

…where n1 and n2 are non negative integers.

Similarly the same can be written for y-direction as:

n3*K1 + n4*K2 = abs(Y1 – Y2),

…where n3 and n4 are non negative integers.

Now, it can be seen that, the problem has been reduced to find if the above equation has solutions or not. If both equations have non-negative solutions then print **‘Yes’**. Otherwise, print **‘No’**.

Below is the implementation of the above approach:

## C++

`// C++ program for the above approach` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Function to check if both can be merged` `int` `twoPointsReachable(` `int` `X1, ` `int` `Y1, ` `int` `X2, ` `int` `Y2,` ` ` `int` `K1, ` `int` `K2)` `{` ` ` `// Calculate gcd of K1, K2` ` ` `int` `g = __gcd(K1, K2);` ` ` `// Solve for the X-axis` ` ` `bool` `reachableOnX = 0;` ` ` `// Calculate distance between the` ` ` `// X-coordinates` ` ` `int` `X_distance = ` `abs` `(X1 - X2);` ` ` `// Check the divisibility` ` ` `if` `(X_distance % g == 0) {` ` ` `reachableOnX = 1;` ` ` `}` ` ` `// Solve for the Y-axis` ` ` `bool` `reachableOnY = 0;` ` ` `// Calculate distance on between` ` ` `// X coordinates` ` ` `int` `Y_distance = ` `abs` `(Y1 - Y2);` ` ` `// Check for the divisibility` ` ` `if` `(Y_distance % g == 0) {` ` ` `reachableOnY = 1;` ` ` `}` ` ` `// Check if both solutions exist` ` ` `if` `(reachableOnY && reachableOnX) {` ` ` `cout << ` `"Yes"` ` ` `<< ` `"\n"` `;` ` ` `}` ` ` `else` `{` ` ` `cout << ` `"No"` ` ` `<< ` `"\n"` `;` ` ` `}` ` ` `return` `0;` `}` `// Driver Code` `int` `main()` `{` ` ` `// Given Input` ` ` `int` `X1 = 10, Y1 = 10, X2 = 18;` ` ` `int` `Y2 = 13, K1 = 3, K2 = 4;` ` ` `// Function Call` ` ` `twoPointsReachable(X1, X2, Y1, Y2, K1, K2);` ` ` `return` `0;` `}` |

## Java

`// Java program for the above approach` `import` `java.util.*;` `public` `class` `GFG{` ` ` ` ` `static` `int` `__gcd(` `int` `a, ` `int` `b)` ` ` `{` ` ` `return` `b == ` `0` `? a : __gcd(b, a % b);` ` ` ` ` `}` `// Function to check if both can be merged` `static` `int` `twoPointsReachable(` `int` `X1, ` `int` `Y1, ` `int` `X2, ` `int` `Y2,` ` ` `int` `K1, ` `int` `K2)` `{` ` ` `// Calculate gcd of K1, K2` ` ` `int` `g = __gcd(K1, K2);` ` ` `// Solve for the X-axis` ` ` `boolean` `reachableOnX = (g == ` `0` `);` ` ` `// Calculate distance between the` ` ` `// X-coordinates` ` ` `int` `X_distance = Math.abs(X1 - X2);` ` ` `// Check the divisibility` ` ` `if` `(X_distance % g == ` `0` `) {` ` ` `reachableOnX = (g == ` `1` `);` ` ` `}` ` ` `// Solve for the Y-axis` ` ` `boolean` `reachableOnY = (g == ` `0` `);` ` ` ` ` `// Calculate distance on between` ` ` `// X coordinates` ` ` `int` `Y_distance = Math.abs(Y1 - Y2);` ` ` `// Check for the divisibility` ` ` `if` `(Y_distance % g == ` `0` `) {` ` ` `reachableOnY = (g == ` `1` `);` ` ` `}` ` ` `// Check if both solutions exist` ` ` `if` `(reachableOnY && reachableOnX) {` ` ` `System.out.print(` `"Yes"` `);` ` ` `}` ` ` `else` `{` ` ` `System.out.print(` `"No"` `);` ` ` `}` ` ` `return` `0` `;` `}` `// Driver Code` `public` `static` `void` `main (String[] args)` `{` ` ` ` ` `// Given Input` ` ` `int` `X1 = ` `10` `, Y1 = ` `10` `, X2 = ` `18` `;` ` ` `int` `Y2 = ` `13` `, K1 = ` `3` `, K2 = ` `4` `;` ` ` `// Function Call` ` ` `twoPointsReachable(X1, X2, Y1,` ` ` `Y2, K1, K2);` `}` `}` `// This code is contributed by shivanisinghss2110` |

## Python3

`# python program for the above approach` `# Function to check if both can be merged` `from` `math ` `import` `*` `def` `twoPointsReachable(X1, Y1, X2, Y2, K1, K2):` ` ` `# Calculate gcd of K1, K2` ` ` `g ` `=` `gcd(K1, K2)` ` ` `# Solve for the X-axis` ` ` `reachableOnX ` `=` `0` ` ` `# Calculate distance between the` ` ` `# X-coordinates` ` ` `X_distance ` `=` `abs` `(X1 ` `-` `X2)` ` ` `# Check the divisibility` ` ` `if` `(X_distance ` `%` `g ` `=` `=` `0` `):` ` ` `reachableOnX ` `=` `1` ` ` `# Solve for the Y-axis` ` ` `reachableOnY ` `=` `0` ` ` `# Calculate distance on between` ` ` `# X coordinates` ` ` `Y_distance ` `=` `abs` `(Y1 ` `-` `Y2)` ` ` `# Check for the divisibility` ` ` `if` `(Y_distance ` `%` `g ` `=` `=` `0` `):` ` ` `reachableOnY ` `=` `1` ` ` `# Check if both solutions exist` ` ` `if` `(reachableOnY ` `and` `reachableOnX):` ` ` `print` `(` `"Yes"` `)` ` ` `else` `:` ` ` `print` `(` `"No"` `)` ` ` `return` `0` `# Driver Code` `# Given Input` `X1 ` `=` `10` `Y1 ` `=` `10` `X2 ` `=` `18` `Y2 ` `=` `13` `K1 ` `=` `3` `K2 ` `=` `4` `# Function Call` `twoPointsReachable(X1, X2, Y1, Y2, K1, K2)` `# This code is contributed by anudeep23042002` |

## C#

`// C++ program for the above approach` `using` `System;` `public` `class` `GFG {` ` ` `static` `int` `__gcd(` `int` `a, ` `int` `b)` ` ` `{` ` ` `return` `b == 0 ? a : __gcd(b, a % b);` ` ` `}` ` ` `// Function to check if both can be merged` ` ` `static` `int` `twoPointsReachable(` `int` `X1, ` `int` `Y1, ` `int` `X2,` ` ` `int` `Y2, ` `int` `K1, ` `int` `K2)` ` ` `{` ` ` `// Calculate gcd of K1, K2` ` ` `int` `g = __gcd(K1, K2);` ` ` `// Solve for the X-axis` ` ` `bool` `reachableOnX = Convert.ToBoolean(0);` ` ` `// Calculate distance between the` ` ` `// X-coordinates` ` ` `int` `X_distance = Math.Abs(X1 - X2);` ` ` `// Check the divisibility` ` ` `if` `(X_distance % g == 0) {` ` ` `reachableOnX = Convert.ToBoolean(1);` ` ` `}` ` ` `// Solve for the Y-axis` ` ` `bool` `reachableOnY = Convert.ToBoolean(0);` ` ` `// Calculate distance on between` ` ` `// X coordinates` ` ` `int` `Y_distance = Math.Abs(Y1 - Y2);` ` ` `// Check for the divisibility` ` ` `if` `(Y_distance % g == 0) {` ` ` `reachableOnY = Convert.ToBoolean(1);` ` ` `}` ` ` `// Check if both solutions exist` ` ` `if` `(reachableOnY && reachableOnX) {` ` ` `Console.Write(` `"Yes"` `);` ` ` `}` ` ` `else` `{` ` ` `Console.Write(` `"No"` `);` ` ` `}` ` ` `return` `0;` ` ` `}` ` ` `// Driver Code` ` ` `public` `static` `void` `Main(String[] args)` ` ` `{` ` ` `// Given Input` ` ` `int` `X1 = 10, Y1 = 10, X2 = 18;` ` ` `int` `Y2 = 13, K1 = 3, K2 = 4;` ` ` `// Function Call` ` ` `twoPointsReachable(X1, X2, Y1, Y2, K1, K2);` ` ` `}` `}` `// This code is contributed by shivanisinghss2110` |

## Javascript

`<script>` ` ` `// JavaScript Program to implement` ` ` `// the above approach` ` ` `function` `__gcd(a, b)` ` ` `{` ` ` ` ` `// Everything divides 0` ` ` `if` `(a == 0)` ` ` `return` `b;` ` ` `if` `(b == 0)` ` ` `return` `a;` ` ` `// base case` ` ` `if` `(a == b)` ` ` `return` `a;` ` ` `// a is greater` ` ` `if` `(a > b)` ` ` `return` `__gcd(a - b, b);` ` ` `return` `__gcd(a, b - a);` ` ` `}` ` ` `// Function to check if both can be merged` ` ` `function` `twoPointsReachable(X1, Y1, X2, Y2,` ` ` `K1, K2) {` ` ` `// Calculate gcd of K1, K2` ` ` `let g = __gcd(K1, K2);` ` ` `// Solve for the X-axis` ` ` `let reachableOnX = 0;` ` ` `// Calculate distance between the` ` ` `// X-coordinates` ` ` `let X_distance = Math.abs(X1 - X2);` ` ` `// Check the divisibility` ` ` `if` `(X_distance % g == 0) {` ` ` `reachableOnX = 1;` ` ` `}` ` ` `// Solve for the Y-axis` ` ` `let reachableOnY = 0;` ` ` `// Calculate distance on between` ` ` `// X coordinates` ` ` `let Y_distance = Math.abs(Y1 - Y2);` ` ` `// Check for the divisibility` ` ` `if` `(Y_distance % g == 0) {` ` ` `reachableOnY = 1;` ` ` `}` ` ` `// Check if both solutions exist` ` ` `if` `(reachableOnY && reachableOnX) {` ` ` `document.write(` `"Yes"` `+ ` `"<br>"` `);` ` ` `}` ` ` `else` `{` ` ` `document.write(` `"No"` `+ ` `"<br>"` `);` ` ` `}` ` ` `return` `0;` ` ` `}` ` ` `// Driver Code` ` ` `// Given Input` ` ` `let X1 = 10, Y1 = 10, X2 = 18;` ` ` `let Y2 = 13, K1 = 3, K2 = 4;` ` ` `// Function Call` ` ` `twoPointsReachable(X1, X2, Y1,` ` ` `Y2, K1, K2);` `// This code is contributed by Potta Lokesh` ` ` `</script>` |

**Output:**

Yes

**Time Complexity: **O(log(max(K1, K2)))**Auxiliary Space: **O(1)