Hướng dẫn is possible hackerrank solution c++ - có thể là giải pháp hackerrank c ++

Định nghĩa vấn đề ngắn:

Adam đang đứng ở điểm & nbsp; [a, b] & nbsp; trong một lưới 2D vô hạn. Anh ta muốn biết nếu anh ta có thể đạt đến điểm & nbsp; [x, y] & nbsp; hoặc không. Hoạt động duy nhất anh ta có thể làm là di chuyển đến điểm & nbsp; [a+b, b] [a, b+a] [a-b, b] hoặc [a, b-a] & nbsp; từ một số điểm & nbsp; [a, b]. Nó được cho là anh ta có thể di chuyển đến bất kỳ điểm nào trên lưới 2D này, tức là, các điểm có tọa độ tích cực hoặc âm & nbsp; [hoặc & nbsp;].

Nói với Adam rằng anh ta có thể tiếp cận & nbsp; & nbsp; hay không.

Liên kết

Có thể là con đường

Complexity:

Độ phức tạp về thời gian là O [log [n]]

Độ phức tạp không gian là O [1]

Execution:

Tuyên bố vấn đề không yêu cầu đường dẫn từ A, B đến X, Y, chỉ là một đường dẫn tồn tại. Điều này làm cho nó một vấn đề toán học.

Chúng tôi biết rằng GCD [A, B] == GCD [A+B, B] == GCD [A-B, B]. Tại sao? Bởi vì nếu một cái gì đó là một ước số D của B, việc thêm/trừ B từ bất kỳ số A nào cũng chia hết bởi D sẽ không thay đổi yêu cầu chia rẽ.

Do đó GCD [a, b] == gcd [a+n*b, b+m*a] trong đó n, m là số nguyên.

Theo các quy tắc, chúng ta có thể nhận ra rằng GCD [A+N*B, B+M*A] là GCD [X, Y], dẫn chúng ta đến giải pháp cuối cùng.

Solution:

def gcd[a, b]:
    if a % b == 0:
        return b
    else:
        return gcd[b, a % b]

def solve[a, b, x, y]:
    return gcd[a,b] == gcd[x,y]

Nếu bạn thích bài đăng này, thì hãy chắc chắn rằng bạn đăng ký nhận bản tin và/hoặc nguồn cấp dữ liệu của tôi.

Mô tả câu hỏi

Bạn được cung cấp một cặp số nguyên [x, y]. Bạn có thể thực hiện một trong hai hoạt động bên dưới, theo bất kỳ thứ tự nào, bằng không hoặc nhiều lần.

1. [x, y] -> [x+y, y] 2. [x, y] -> [x, y+x]
2. [x,y] -> [x,y+x]

Ví dụ: bạn có thể bắt đầu với [1, 4], thay đổi nó thành [5, 4], thay đổi điều đó thành [5, 9], sau đó thay đổi lại thành [5, 14]. Bạn được cho bốn số nguyên: a, b, c và d. Trả về Có Có Có [không có trích dẫn] nếu có thể bắt đầu với cặp [A, B] và kết thúc với cặp [C, D]. Nếu không, hãy trả lại không có.
You are given four integers: a, b, c, and d. Return “Yes” [without quotes] if it is possible to start with the pair [a, b] and end with the pair [c, d]. Otherwise, return “No”.

Chữ ký phương thức: chuỗi isitpossible [int a, int b, int c, int d]

Đầu vào bốn số nguyên trong các dòng riêng biệt.
Four integers in separate lines.

Đầu ra một chuỗi có thể có.
One string “Yes” or “No”.

Hạn chế

1≤ a, b, c, d ≤ 1000

Mẫu đầu vào 1 4 5 9
1
4
5
9

Đầu ra mẫu Có
Yes

Giải thích [1, 4] -> [5, 4] -> [5, 9].
[1, 4] -> [5, 4] -> [5, 9] .

Giải pháp trong Java

static LinkedList pairs = new LinkedList[];

    public static String isItPossible[Integer a, Integer b, Integer c, Integer d]{
        pairs.addLast[new Pair[a,b]];
        while [!pairs.isEmpty[]]{
            Pair pair = pairs.poll[];
            Integer key = pair.getKey[];
            Integer value = pair.getValue[];
            if[key.equals[a] &&
                    value.equals[b]]{
                return "YES";
            }
            int sum=key+value;
            if [sum

Bài Viết Liên Quan

Toplist mới

Bài mới nhất

Chủ Đề