Діапазон LCM-запитів  


Рівень складності Жорсткий
Часто запитують у Амазонка Directi Google Дійсно PayPal Snapdeal Убер
масив Проблема запиту Дерево сегментів Дерево

Постановка проблеми  

У проблемі "Діапазон запитів LCM" зазначено, що у вас є ціле масив і 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-запитівPin

 

Алгоритм  

  1. Заявіть два з масиви.
  2. Побудуйте a дерево сегментів шляхом рекурсивного виклику функцій для лівої та правої дитини.
  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 цих двох значень і поверніть це значення.

Дивись також
Домашнє Розбійник II Рішення Leetcode

код  

Код C ++ для запитів Range 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 для запитів Range 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 (Журнал N * Журнал n) де "N" - кількість елементів у масиві. Інші журнал n позначає час, необхідний для пошуку LCM. Ця складність часу стосується кожного запиту. Загальна складність часу становить O (N + Q * Log N * log n), це тому, що для побудови дерева, а потім для відповіді на запити, потрібен O ​​(N) час.

Дивись також
Сума шляху

Складність простору

 O (N) де "N" - кількість елементів у масиві. Цей простір необхідний для зберігання дерева сегментів.