GCD δεδομένου εύρους ευρετηρίου σε έναν πίνακα


Επίπεδο δυσκολίας Σκληρά
Συχνές ερωτήσεις DE Shaw PayPal Snapchat Snapdeal Times Internet Xome
Παράταξη Πρόβλημα ερωτήματος Τμήμα-δέντρο Δέντρο

Δήλωση προβλήματος

Το πρόβλημα «GCDs δεδομένου εύρους ευρετηρίου σε έναν πίνακα» δηλώνει ότι σας δίνεται ένα ακέραιος αριθμός παράταξη και ορισμένα ερωτήματα εύρους. Η δήλωση προβλήματος ζητά να ανακαλύψει τον Μεγαλύτερο Κοινό Διαχωριστή της υπο-συστοιχίας που σχηματίζεται εντός του εύρους.

Παράδειγμα

arr[] = {10, 5, 18, 9, 24}
Query: {(0, 1), (2, 4), (0, 3)}
5 3 1

εξήγηση

Ο μεγαλύτερος κοινός διαιρέτης του πρώτου ερωτήματος κυμαίνεται από 0 και 1, επομένως το GCD των 10 και 5 είναι 5.

Το GCD του δεύτερου ερωτήματος κυμαίνεται από 2 και 4, επομένως το GCD των 18, 9, 24 είναι 3.

Ο μεγαλύτερος κοινός διαιρέτης του πρώτου ερωτήματος κυμαίνεται από 0 και 3, επομένως το GCD είναι 1.

GCD δεδομένου εύρους ευρετηρίου σε έναν πίνακα

 

Αλγόριθμος

  1. Ξεκινήστε με μια ενότητα arr [0] έως arr [n-1] και συνεχίστε την κατάτμηση σε ίσα μέρη. Κάθε φορά που χωρίζουμε την τρέχουσα ενότητα σε ίσα μέρη. Στη συνέχεια, ζητήστε αναδρομικά τα δύο μέρη. Και για κάθε τέτοιο τμήμα, αποθηκεύουμε τη μεγαλύτερη κοινή τιμή διαιρέτη σε ένα δέντρο τμημάτων.
  2. Δημιουργήστε ένα δέντρο τμημάτων που θα γεμίσει εκτός από το τελευταίο επίπεδο.
  3. Κάθε κόμβος του δέντρου τμημάτων αποθηκεύει το GCD όλων των στοιχείων που αντιστοιχούν σε ένα συγκεκριμένο εύρος.
  4. Για να μάθετε το ερώτημα του GCD, εάν το εύρος του κόμβου θα είναι στο startQuery και στο endQuery, τότε επιστρέψτε την τιμή στον κόμβο.
  5. Διαφορετικά εάν, το εύρος δεν είναι έγκυρο, τότε επιστρέψτε το μηδέν ή -1.
  6. Διαφορετικά επιστρέφετε την αναδρομική κλήση της λειτουργίας GCD.

εξήγηση

Μας δίνεται ένα ακέραιος αριθμός παράταξη και q αριθμός ερωτημάτων. Κάθε ερώτημα περιέχει το εύρος ως startQuery και endQuery. Μέσα σε αυτό το εύρος, πρέπει να βρούμε τον μεγαλύτερο κοινό διαιρέτη όλων των αριθμών που ικανοποιούν το δεδομένο εύρος. Για αυτό θα χτίσουμε το τμήμα δέντρο, θα λύσουμε τα ερωτήματα στον αποτελεσματικό χρόνο του log N * log n.

Θα αρχίσουμε να χτίζουμε το δέντρο τμημάτων από την 0η θέση του πίνακα στην τελευταία θέση του πίνακα, και το σημαντικό μέρος είναι η διαίρεση του πίνακα σε δύο μισά. Θα συνεχίσουμε να το διαιρούμε μέχρι το μήκος του πίνακα να είναι ένα, και στη συνέχεια στο επόμενο βήμα να καλέσουμε αναδρομικά τη συνάρτηση και στα δύο μέρη του πίνακα. Εδώ θα αποθηκεύσουμε τον μεγαλύτερο κοινό διαιρέτη σε έναν κόμβο δέντρου. Όλοι οι εσωτερικοί κόμβοι δεν θα είναι μηδενικοί, εκτός από τους κόμβους φύλλων. Το δέντρο που σχηματίζεται έτσι θα είναι ένα δυαδικό δέντρο. Επειδή υπάρχουν δύο μέρη του πίνακα σε κάθε επίπεδο κόμβου. Αλλά σε σύγκριση με ένα δυαδικό δέντρο, όπου οι κόμβοι αντιπροσωπεύουν ένα εύρος αντί για έναν μόνο αριθμό.

Για κάθε ερώτημα του Greatest Common Divisor που δίνεται, ελέγχουμε εάν το εύρος του κόμβου βρίσκεται εντός του εύρους startQuery και του endQuery. Στη συνέχεια, θα επιστρέψουμε την τιμή στον κόμβο του δέντρου τμημάτων. Έχουμε επίσης μια δεύτερη συνθήκη όπου εάν το εύρος του κόμβου είναι εκτός του εύρους startQuery range και το endQuery range. Τότε θα επιστρέψουμε την τιμή -1 ή null. Και για να κάνουμε τη λειτουργία συνεχώς προοδευτική, θα καλέσουμε αναδρομικά τον κόμβο τόσο παιδί, αριστερά όσο και δεξιά. Στη συνέχεια, μάθετε τον μεγαλύτερο κοινό διαιρέτη της επιστρεφόμενης τιμής από τους κόμβους.

Κώδικας

Κωδικός C ++ για εύρεση GCD συγκεκριμένων περιοχών ευρετηρίου σε έναν πίνακα

#include<iostream>
#include<math.h>

using namespace std;

int *segTree;

int gcd(int a, int b)
{
    if (a < b)
    {
        int temp = b;
        b = a;
        a = temp;
    }

    if (b==0)
        return a;
    return gcd(b,a%b);
}

int getGCDOfNumber(int startNode, int endNode, int startQuery, int endQuery, int si)
{
    if (startNode>endQuery || endNode < startQuery)
        return 0;
    if (startQuery<=startNode && endQuery>=endNode)
        return segTree[si];

    int mid = startNode+(endNode-startNode)/2;

    return gcd(getGCDOfNumber(startNode, mid, startQuery, endQuery, si*2+1),
               getGCDOfNumber(mid+1, endNode, startQuery, endQuery, si*2+2));
}

int findRangeGcd(int startNode, int endNode, int arr[],int n)
{
    if (startNode<0 || endNode > n-1 || startNode>endNode)
    {
        cout << "Invalid Arguments" << "\n";
        return -1;
    }
    return getGCDOfNumber(0, n-1, startNode, endNode, 0);
}

int buildSegementTree(int arr[], int startNode, int endNode, int si)
{
    if (startNode==endNode)
    {
        segTree[si] = arr[startNode];
        return segTree[si];
    }
    int mid = startNode+(endNode-startNode)/2;

    segTree[si] = gcd(buildSegementTree(arr, startNode, mid, si*2+1),
                      buildSegementTree(arr, mid+1, endNode, si*2+2));
    return segTree[si];
}

int *constructendNodegmentTree(int arr[], int n)
{
    int height = (int)(ceil(log2(n)));
    int size = 2*(int)pow(2, height)-1;
    segTree = new int[size];
    buildSegementTree(arr, 0, n-1, 0);
    return segTree;
}

int main()
{
    int a[] = {10, 5, 18, 9, 24};
    int n = sizeof(a)/sizeof(a[0]);

    constructendNodegmentTree(a, n);

    int l = 0, r = 1;
    cout << "Greatest Common Divisor is: ";
    cout << findRangeGcd(l, r, a, n) << "\n";

    l = 2;
    r = 4;
    cout << "Greatest Common Divisor is: ";
    cout << findRangeGcd(l, r, a, n) << "\n";

    l = 0;
    r = 3;
    cout << "Greatest Common Divisor is: ";
    cout << findRangeGcd(l, r, a, n) << "\n";

    return 0;
}
Greatest Common Divisor is: 5
Greatest Common Divisor is: 3
Greatest Common Divisor is: 1

Κωδικός Java για την εύρεση GCD δεδομένων περιοχών ευρετηρίου σε έναν πίνακα

import java.io.*;

public class GCDOfNumber
{
    private static int[] segTree;

    public static int[] buildSegmentTree(int[] arr)
    {
        int height = (int)Math.ceil(Math.log(arr.length)/Math.log(2));
        int size = 2*(int)Math.pow(2, height)-1;
        segTree = new int[size];
        SegementTree(arr, 0, arr.length-1, 0);

        return segTree;
    }

    public static int SegementTree(int[] arr, int startNode,
                                   int endNode, int si)
    {
        if (startNode==endNode)
        {
            segTree[si] = arr[startNode];

            return segTree[si];
        }
        int mid = startNode+(endNode-startNode)/2;

        segTree[si] = gcd(SegementTree(arr, startNode, mid, si*2+1),
                          SegementTree(arr, mid+1, endNode, si*2+2));
        return segTree[si];
    }

    private static int gcd(int a, int b)
    {
        if (a < b)
        {
            int temp = b;
            b = a;
            a = temp;
        }

        if (b==0)
            return a;
        return gcd(b,a%b);
    }

    public static int findRangeGcd(int startNode, int endNode, int[] arr)
    {
        int n = arr.length;

        if (startNode<0 || endNode > n-1 || startNode>endNode)
            throw new IllegalArgumentException("Invalid arguments");

        return findGcd(0, n-1, startNode, endNode, 0);
    }

    public static int findGcd(int startNode, int endNode, int startQuery, int endQuery, int si)
    {
        if (startNode>endQuery || endNode < startQuery)
            return 0;

        if (startQuery<=startNode && endQuery>=endNode)
            return segTree[si];

        int mid = startNode+(endNode-startNode)/2;

        return gcd(findGcd(startNode, mid, startQuery, endQuery, si*2+1),
                   findGcd(mid+1, endNode, startQuery, endQuery, si*2+2));
    }

    public static void main(String[] args)throws IOException
    {
        int[] a = {10, 5, 18, 9, 24};

        buildSegmentTree(a);

        int l = 0, r = 1;
        System.out.println("Greatest Common Divisor is: "+findRangeGcd(l, r, a));

        l = 2;
        r = 4;
        System.out.println("Greatest Common Divisor is: "+findRangeGcd(l, r, a));

        l = 0;
        r = 3;
        System.out.println("Greatest Common Divisor is: "+findRangeGcd(l, r, a));
    }
}
Greatest Common Divisor is: 5
Greatest Common Divisor is: 3
Greatest Common Divisor is: 1

Ανάλυση πολυπλοκότητας

Χρόνος πολυπλοκότητας

O (n log n + log n * log (min (a, b))) όπου «Ν» είναι ο αριθμός των κόμβων και "Α" "σι" είναι κόμβοι των οποίων το GCD υπολογίζεται κατά τη λειτουργία συγχώνευσης. O (n logn) αφιερώνεται χρόνος για κατασκευή και O (ημερολόγιο n) για να απαντήσετε σε κάθε ερώτημα και στη συνέχεια O (log (min (a, b))) ώρα για εύρεση gcd.

Διαστημική πολυπλοκότητα

O (n) όπου «Ν» είναι οι κόμβοι. Ο χώρος ξοδεύεται στην κατασκευή ενός τμήματος δέντρου.