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

Question

Đị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 dung chính Show

bài chuyển hướng
Có giải pháp nào trên HackerRank không?
Chúng ta có thể sao chép mã dán trong HackerRank không?
Hackerrank có thể phát hiện gian lận không?
Bạn có thể sử dụng bất kỳ ngôn ngữ nào trong HackerRank không?

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<=c){
                pairs.addLast(new Pair(sum,value));
            }
            if (sum<=d){
                pairs.addLast(new Pair(key,sum));
            }

        }

        return "NO";
    }

bài chuyển hướng

Nếu tất cả các con số phải là tích cực, thì tôi tin rằng có một giải pháp nhanh hơn nhiều.

Cố gắng tìm xem nếu chúng ta có thể nhận được từ (a, b) đến, nói (14, 31), chúng ta có thể lưu ý rằng cách duy nhất với các số dương để đạt được (14, 31) là áp dụng quy tắc thứ hai cho (14, 17). Cách duy nhất để đến (14, 17) là áp dụng quy tắc thứ hai cho (14, 3). Cách duy nhất để đến (14, 3) là áp dụng quy tắc đầu tiên cho

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<=c){
                pairs.addLast(new Pair(sum,value));
            }
            if (sum<=d){
                pairs.addLast(new Pair(key,sum));
            }

        }

        return "NO";
    }

0. Cách duy nhất để

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<=c){
                pairs.addLast(new Pair(sum,value));
            }
            if (sum<=d){
                pairs.addLast(new Pair(key,sum));
            }

        }

        return "NO";
    }

0 là áp dụng quy tắc đầu tiên cho

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<=c){
                pairs.addLast(new Pair(sum,value));
            }
            if (sum<=d){
                pairs.addLast(new Pair(key,sum));
            }

        }

        return "NO";
    }

2, v.v. Vì vậy, các giá trị duy nhất có thể đạt được (14, 31) là

(14, 31) # Final
(14, 17) # Rule 2
(14, 3)  # Rule 2
(11, 3)  # Rule 1
(8, 3)   # Rule 1
(5, 3)   # Rule 1
(2, 3)   # Rule 1
(2, 1)   # Rule 2
(1, 1)   # Rule 1

Vì vậy, một thuật toán khá đơn giản. Vòng lặp trên

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<=c){
                pairs.addLast(new Pair(sum,value));
            }
            if (sum<=d){
                pairs.addLast(new Pair(key,sum));
            }

        }

        return "NO";
    }

4, thay thế nó bằng

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<=c){
                pairs.addLast(new Pair(sum,value));
            }
            if (sum<=d){
                pairs.addLast(new Pair(key,sum));
            }

        }

        return "NO";
    }

5 nếu

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<=c){
                pairs.addLast(new Pair(sum,value));
            }
            if (sum<=d){
                pairs.addLast(new Pair(key,sum));
            }

        }

        return "NO";
    }

6 và với

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<=c){
                pairs.addLast(new Pair(sum,value));
            }
            if (sum<=d){
                pairs.addLast(new Pair(key,sum));
            }

        }

        return "NO";
    }

7 nếu

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<=c){
                pairs.addLast(new Pair(sum,value));
            }
            if (sum<=d){
                pairs.addLast(new Pair(key,sum));
            }

        }

        return "NO";
    }

8, hãy dừng khi bạn đánh một trận đấu, khi

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<=c){
                pairs.addLast(new Pair(sum,value));
            }
            if (sum<=d){
                pairs.addLast(new Pair(key,sum));
            }

        }

        return "NO";
    }

9, khi

(14, 31) # Final
(14, 17) # Rule 2
(14, 3)  # Rule 2
(11, 3)  # Rule 1
(8, 3)   # Rule 1
(5, 3)   # Rule 1
(2, 3)   # Rule 1
(2, 1)   # Rule 2
(1, 1)   # Rule 1

0 hoặc

(14, 31) # Final
(14, 17) # Rule 2
(14, 3)  # Rule 2
(11, 3)  # Rule 1
(8, 3)   # Rule 1
(5, 3)   # Rule 1
(2, 3)   # Rule 1
(2, 1)   # Rule 2
(1, 1)   # Rule 1

1.

Một biến thể của điều này được mô tả trong một bình luận của Paul Hankin là

(14, 31) # Final
(14, 17) # Rule 2
(14, 3)  # Rule 2
(11, 3)  # Rule 1
(8, 3)   # Rule 1
(5, 3)   # Rule 1
(2, 3)   # Rule 1
(2, 1)   # Rule 2
(1, 1)   # Rule 1

2, mặc dù tôi sẽ không cố gắng chứng minh điều đó. Phiên bản này là

(14, 31) # Final
(14, 17) # Rule 2
(14, 3)  # Rule 2
(11, 3)  # Rule 1
(8, 3)   # Rule 1
(5, 3)   # Rule 1
(2, 3)   # Rule 1
(2, 1)   # Rule 2
(1, 1)   # Rule 1

3, trong đó

(14, 31) # Final
(14, 17) # Rule 2
(14, 3)  # Rule 2
(11, 3)  # Rule 1
(8, 3)   # Rule 1
(5, 3)   # Rule 1
(2, 3)   # Rule 1
(2, 1)   # Rule 2
(1, 1)   # Rule 1

4 là lớn hơn của

(14, 31) # Final
(14, 17) # Rule 2
(14, 3)  # Rule 2
(11, 3)  # Rule 1
(8, 3)   # Rule 1
(5, 3)   # Rule 1
(2, 3)   # Rule 1
(2, 1)   # Rule 2
(1, 1)   # Rule 1

5 và

(14, 31) # Final
(14, 17) # Rule 2
(14, 3)  # Rule 2
(11, 3)  # Rule 1
(8, 3)   # Rule 1
(5, 3)   # Rule 1
(2, 3)   # Rule 1
(2, 1)   # Rule 2
(1, 1)   # Rule 1

6. Số Fibonacci liên tiếp có thể sẽ thực hiện nhiều bước nhất.

Tất nhiên tất cả điều này là vô nghĩa nếu bạn có thể có số âm, vì quy tắc đầu tiên được áp dụng cho

(14, 31) # Final
(14, 17) # Rule 2
(14, 3)  # Rule 2
(11, 3)  # Rule 1
(8, 3)   # Rule 1
(5, 3)   # Rule 1
(2, 3)   # Rule 1
(2, 1)   # Rule 2
(1, 1)   # Rule 1

7 cũng sẽ mang lại (14, 31) và bạn trở lại theo cấp số nhân.

Có giải pháp nào trên HackerRank không?

Các thách thức lập trình của HackerRank có thể được giải quyết bằng nhiều ngôn ngữ lập trình khác nhau (bao gồm Java, C ++, PHP, Python, SQL, JavaScript) và bao gồm nhiều lĩnh vực khoa học máy tính. Khi một lập trình viên gửi một giải pháp cho một thách thức lập trình, bài nộp của họ được tính vào tính chính xác của đầu ra của họ.. When a programmer submits a solution to a programming challenge, their submission is scored on the accuracy of their output.

Chúng ta có thể sao chép mã dán trong HackerRank không?

Bản sao/Dán theo dõi Nếu một ứng cử viên dán mã được sao chép trong đánh giá, bạn có thể xem mã được dán trong báo cáo kiểm tra của ứng viên.Ngoài ra, nếu ứng viên cố gắng dán mã từ các nguồn khác, nó sẽ được nắm bắt trong mô hình đạo văn của chúng tôi.If a candidate pastes a copied code in the assessment, you can view that pasted code in the candidate's test report. Also, if the candidate tries to paste the code from other sources, it will be captured in our plagiarism model.

Hackerrank có thể phát hiện gian lận không?

Hackerrank cho phép kiểm tra kiểm tra và kiểm tra đạo văn để đảm bảo rằng ứng viên không gian lận..

Bạn có thể sử dụng bất kỳ ngôn ngữ nào trong HackerRank không?

HackerRank cho công việc hiện đang hỗ trợ hơn 40 ngôn ngữ lập trình khác nhau.Để thúc đẩy các thực tiễn mã hóa tối ưu trong các bài kiểm tra HackerRank và các cuộc phỏng vấn trực tuyến, môi trường mã hóa của chúng tôi có giới hạn thời gian và bộ nhớ đặt trước để thực hiện mã trong mỗi ngôn ngữ lập trình.. To promote optimal coding practices in HackerRank Tests and online interviews, our coding environment has preset time and memory limits for code execution in each programming language.

programming c++ HackerRank C solutions HackerRank Is possible LeetCode

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:

Liên kết

Complexity:

Execution:

Solution:

bài chuyển hướng

Có giải pháp nào trên HackerRank không?

Chúng ta có thể sao chép mã dán trong HackerRank không?

Hackerrank có thể phát hiện gian lận không?

Bạn có thể sử dụng bất kỳ ngôn ngữ nào trong HackerRank không?

Bài Viết Liên Quan

Quảng Cáo

Có thể bạn quan tâm

Toplist được quan tâm

Quảng cáo

Xem Nhiều

Quảng cáo

Chúng tôi

Điều khoản

Trợ giúp

Mạng xã hội