Ερώτηση εύρους LCM


Επίπεδο δυσκολίας Σκληρά
Συχνές ερωτήσεις αμαζόνα Σκηνοθεσία Google Πράγματι PayPal Snapdeal Uber
Παράταξη Πρόβλημα ερωτήματος Τμήμα-δέντρο Δέντρο

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

Το πρόβλημα "Range LCM Queries" δηλώνει ότι έχετε ακέραιος αριθμός παράταξη q αριθμός ερωτημάτων Κάθε ερώτημα περιέχει το (αριστερά, δεξιά) ως εύρος. Η δεδομένη εργασία είναι να μάθετε το LCM (αριστερά, δεξιά), δηλαδή, το LCM όλων των αριθμών που περιλαμβάνονται στο εύρος αριστερά και δεξιά.

Παράδειγμα

arr[] = {2, 4, 6, 9, 10, 8, 7, 5, 14, 1};
Query: {(2, 5), (3, 7), (5, 8)}
360 2520 280

εξήγηση

για (2,5) το LCM των 6,9,10 και 8 είναι 360

Τώρα και πάλι για το επόμενο ερώτημα, δηλαδή, (3,7), το LCM 9,10,8,7 και 5 είναι 2520

και επιτέλους για (5,8) LCM 8,7,5 και 14 θα είναι 280

Ερώτηση εύρους LCM

 

Αλγόριθμος

  1. Δηλώστε δύο από τα συστοιχίες.
  2. Φτιάξτε ένα δέντρο τμημάτων καλώντας αναδρομικά τις λειτουργίες για το αριστερό παιδί και το δεξί παιδί.
  3. Λάβετε το LCM για τον αριστερό θυγατρικό κόμβο και τον δεξιό θυγατρικό κόμβο.
  4. Για να λάβετε το LCM ενός αριθμού, διαιρέστε το προϊόν του αριστερού παιδιού και του δεξιού παιδιού με το GCD τους.
  5. Για κάθε ερώτημα ως αριστερά και δεξιά, ελέγξτε εάν το εύρος δεν είναι έγκυρο και επιστρέψτε 1, αλλιώς ελέγξτε αν το αριστερό είναι μικρότερο από την αρχική τιμή του κόμβου και το δεξί είναι μεγαλύτερο από την τιμή του τελικού κόμβου και, στη συνέχεια, επιστρέψτε το τρέχων κόμβος τιμής του δέντρου.
  6. Εάν κάποια από τις παραπάνω συνθήκες δεν ισχύει, αλλιώς καλέστε αναδρομικά τη συνάρτηση για να λάβετε τον αριστερό κόμβο lcm και τον δεξιό κόμβο lcm και στη συνέχεια καλέστε τη συνάρτηση lcm για να λάβετε το LCM αυτών των αριθμών.

εξήγηση

Δίνεται ένας ακέραιος πίνακας και κάποιο ερώτημα με αριστερό και δεξιό εύρος. Μάθετε το LCM όλων των αριθμών εντός του εύρους. Για να μάθετε το lcm εφαρμόστε τον τύπο ως LCM του arr [αριστερά, αριστερά + 1, ……., Δεξιά-1, δεξιά], αλλά σε αυτό, θα χρησιμοποιούμε ένα δέντρο. Θα χτίσουμε ένα δέντρο τμημάτων. Θα ελέγξουμε εάν υπάρχει μόνο μία τιμή σε έναν πίνακα και, στη συνέχεια, εισάγουμε τη συγκεκριμένη τιμή στον κόμβο του δέντρου. Αλλιώς, θα χωρίσουμε τη συστοιχία στα δύο και θα αρχίσουμε να χτίζουμε το δέντρο, για τον αριστερό θυγατρικό κόμβο. Στη συνέχεια, μεταβιβάστε τις τιμές ως κόμβο 2 * για αριστερό κόμβο και για δεξιό θυγατρικό κόμβο, 2 * κόμβος + 1 και λάβετε το LCM αυτών των τιμών μεταβιβάζοντάς το στη συνάρτηση getLCM. Και λάβετε το LCM αυτών των δύο θυγατρικών κόμβων και αποθηκεύστε αυτήν την επιστρεφόμενη τιμή στη θέση κόμβου του δέντρου.

Στη συνάρτηση LCM, θα βρούμε τον μεγαλύτερο κοινό διαιρέτη των τιμών του αριστερού και του δεξιού κόμβου. Τότε θα επιστρέψουμε το προϊόν της διαίρεσης του προϊόντος του αριστερού και του δεξιού κόμβου και του μεγαλύτερου κοινού διαιρέτη του αριστερού και του δεξιού κόμβου.

Για κάθε ερώτημα που θα λάβουμε ως αριστερή και δεξιά θέση, θα ελέγξουμε ξανά την εγκυρότητα του εύρους εάν η τελική τιμή είναι μικρότερη από την αριστερή ή η τιμή έναρξης είναι μεγαλύτερη από τη δεξιά και μετά επιστροφή 1, είναι μια άκυρη ερώτηση. Διαφορετικά, θα ελέγξουμε την εγκυρότητα εάν το αριστερό και το δεξί είναι λιγότερο ίσο με και μεγαλύτερο από το ίδιο με την αρχή και το τέλος αντίστοιχα, και στη συνέχεια θα επιστρέψουμε την τιμή του δέντρου στον κόμβο. Λάβετε την τιμή του αριστερού παιδιού και τη δεξιά τιμή του παιδιού και λάβετε το LCM αυτών των δύο τιμών και επιστρέψτε αυτήν την τιμή.

Κώδικας

Κωδικός C ++ για ερωτήματα εύρους LCM

#include<iostream>

using namespace std;

#define MAX 1000

int tree[4*MAX];

int arr[MAX];

int GCD(int a, int b)
{
    if (a == 0)
        return b;
    return GCD(b%a, a);
}
int getLCM(int a, int b)
{
    return a*b/GCD(a,b);
}
int solveQuery(int node, int start, int end, int left, int right)
{
    if (end < left || start > right)
        return 1;

    if (left<=start && right >=end)
        return tree[node];

    int mid = (start+end)/2;
    int leftChildgetLCM = solveQuery(2*node, start, mid, left, right);
    int rightChildgetLCM = solveQuery(2*node+1, mid+1, end, left, right);
    return getLCM(leftChildgetLCM, rightChildgetLCM);
}
void buildTree(int node, int start, int end)
{
    if (start==end)
    {
        tree[node] = arr[start];
        return;
    }

    int mid = (start+end)/2;
    buildTree(2*node, start, mid);
    buildTree(2*node+1, mid+1, end);

    int leftChildgetLCM = tree[2*node];
    int rightChildgetLCM = tree[2*node+1];

    tree[node] = getLCM(leftChildgetLCM, rightChildgetLCM);
}

int main()
{
    arr[0] = 2;
    arr[1] = 4;
    arr[2] = 6;
    arr[3] = 9;
    arr[4] = 10;
    arr[5] = 8;
    arr[6] = 7;
    arr[7] = 5;
    arr[8] = 14;
    arr[9] = 1;
    buildTree(1, 0, 9);
    cout << solveQuery(1, 0, 9, 2, 5) << endl;

    cout << solveQuery(1, 0, 9, 3, 7) << endl;

    cout << solveQuery(1, 0, 9, 5, 8) << endl;

    return 0;
}
360
2520
280

Κωδικός Java για ερωτήματα εύρους LCM

class LCMQueries
{

    private static final int MAX = 1000;

    private static int tree[] = new int[4 * MAX];

    private static int arr[] = new int[MAX];

    static int GCD(int a, int b)
    {
        if (a == 0)
        {
            return b;
        }
        return GCD(b % a, a);
    }
    static int getLCM(int a, int b)
    {
        return a * b / GCD(a, b);
    }
    static void buildTree(int node, int start, int end)
    {
        if (start == end)
        {
            tree[node] = arr[start];
            return;
        }

        int mid = (start + end) / 2;
        buildTree(2 * node, start, mid);
        buildTree(2 * node + 1, mid + 1, end);
        int leftChildLCM = tree[2 * node];
        int rightChildLCM = tree[2 * node + 1];

        tree[node] = getLCM(leftChildLCM, rightChildLCM);
    }
    static int solveQuery(int node, int start,
                          int end, int left, int right)
    {
        if (end < left || start > right)
        {
            return 1;
        }

        if (left <= start && right >= end)
        {
            return tree[node];
        }

        int mid = (start + end) / 2;
        int leftChildLCM = solveQuery(2 * node, start, mid, left, right);
        int rightChildLCM = solveQuery(2 * node + 1, mid + 1, end, left, right);
        return getLCM(leftChildLCM, rightChildLCM);
    }
    public static void main(String[] args)
    {
        arr[0] = 2;
        arr[1] = 4;
        arr[2] = 6;
        arr[3] = 9;
        arr[4] = 10;
        arr[5] = 8;
        arr[6] = 7;
        arr[7] = 5;
        arr[8] = 14;
        arr[9] = 1;

        buildTree(1, 0, 9);

        System.out.println(solveQuery(1, 0, 9, 2, 5));

        System.out.println(solveQuery(1, 0, 9, 3, 7));

        System.out.println(solveQuery(1, 0, 9, 5, 8));

    }
}
360
2520
280

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

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

 O (Log N * Log n) όπου "N" είναι ο αριθμός των στοιχείων στον πίνακα. Το άλλο ημερολόγιο n δηλώνει το χρόνο που απαιτείται για την εύρεση του LCM. Αυτή η πολυπλοκότητα χρόνου είναι για κάθε ερώτημα. Η συνολική χρονική πολυπλοκότητα είναι O (N + Q * Log N * log n), Αυτό συμβαίνει επειδή απαιτείται χρόνος O (N) για την κατασκευή του δέντρου και στη συνέχεια για την απάντηση στα ερωτήματα.

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

 ΕΠΙ) όπου "N" είναι ο αριθμός των στοιχείων στον πίνακα. Αυτός ο χώρος απαιτείται για την αποθήκευση του δέντρου τμημάτων.