Rectangle matrices

You are given a rectangle matrix of size 1018×1018. The rows of the matrix are numbered 1 to 1018 from top to bottom and the columns of the matrix are numbered 1 to 1018 from left to right. The cell of the field at the intersection of the xth row and yth column is represented by (x,y)

A rabbit is standing at cell (1,1). The rabbit can move from a cell (x,y) to a cell (2×x,y) or (x,2×y) in a few seconds because of its good speed. Also, it can move to (x,yx) or (xy,y)

Note: The rabbit cannot move out of the bounds of the matrix.

You purchase food for the rabbit for the next q days. You place the food in the cell (xi,yi) on the ith day but you are unsure if these cells are reachable. Your task is to determine if you can reach from the cell (1,1) to the cell (xi,yi).

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 = { { 11 }, { 22 }, { 36 }, { 47 }, { 10001000 } };
        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");
            } else
                System.out.println("No");
        }

    }

    public static long GCD(long along b) {
        if (a == 0)
            return b;
        else if (b == 0)
            return a;
        else if (a <= b) {
            return GCD(a, b % a);
        } else
            return GCD(a % b, b);
    }

}


No comments:

Post a Comment