You are given a rectangle matrix of size . The rows of the matrix are numbered to from top to bottom and the columns of the matrix are numbered to from left to right. The cell of the field at the intersection of the row and column is represented by .
A rabbit is standing at cell . The rabbit can move from a cell to a cell or in a few seconds because of its good speed. Also, it can move to or .
Note: The rabbit cannot move out of the bounds of the matrix.
You purchase food for the rabbit for the next days. You place the food in the cell on the day but you are unsure if these cells are reachable. Your task is to determine if you can reach from the cell to the cell .
Example:
Input: 5
1 1
2 2
3 6
4 7
1000 1000
Output: Yes
Yes
No
Yes
No
Approach
Java
public class RectangleMatrices {public static void main(String[] args) {int n = 5;long[][] arr2D = { { 1, 1 }, { 2, 2 }, { 3, 6 }, { 4, 7 }, { 1000, 1000 } };for (int i = 0; i < n; i++) {long a = arr2D[i][0], b = arr2D[i][1];long gcd = GCD(a, b);if ((gcd & (gcd - 1)) == 0) {System.out.println("Yes");} elseSystem.out.println("No");}}public static long GCD(long a, long b) {if (a == 0)return b;else if (b == 0)return a;else if (a <= b) {return GCD(a, b % a);} elsereturn GCD(a % b, b);}}
No comments:
Post a Comment