範圍LCM查詢  


難度級別
經常問 亞馬遜 指令 谷歌 確實 貝寶 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)6,9,10和8的LCM為360

現在再次用於下一個查詢,即(3,7),9,10,8,7、5、2520、XNUMX和XNUMX的LCM為XNUMX

最後,對於(5,8),8,7,5和14的LCM將為280

範圍LCM查詢

 

算法  

  1. 聲明兩個 數組.
  2. 建立一個 段樹 通過遞歸調用左側孩子和右側孩子的函數。
  3. 獲取左子節點和右子節點的LCM。
  4. 要獲取數字的LCM,請用左孩子和右孩子的乘積除以他們的GCD。
  5. 對於左右兩個查詢,檢查範圍是否無效,然後返回1,否則檢查左邊是否小於節點的起始值,右邊是否大於結束節點的值,然後返回樹的當前值節點。
  6. 如果以上任一條件都不成立,則遞歸調用該函數以獲取左節點lcm和右節點lcm,然後調用lcm函數以獲取這些數字的LCM。
也可以看看
使用兩個堆棧的迭代後序遍歷

解釋

給定一個整數數組和一些具有左右範圍的查詢。 找出 LCM 範圍內(含)的所有數字。 為了找出lcm,將公式實現為arr [left,left + 1,……。,right-1,right]的LCM,但是在此,我們將使用一棵樹。 我們將要構建一個段樹。 我們將檢查數組中是否只有一個值,然後將該特定值插入樹的節點中。 否則,我們將數組拆分為一半,並開始為左子節點構建樹。 然後,將值作為左節點的2 *節點傳遞,對於右子節點的2 *節點+1傳遞,並將這些值的LCM傳遞給getLCM函數。 並獲得這兩個子節點的LCM,並將返回的值存儲在樹的節點位置。

在LCM函數中,我們將找到該左右節點值的最大公約數。 然後,我們將返回左節點和右節點乘積與左節點和右節點的最大公約數的除法乘積。

對於每個查詢,我們將獲得左右位置,如果結束值小於左邊或起始值大於右邊,我們將再次檢查範圍的有效性,然後返回1,這是一個無效問題。 否則,如果left和right分別小於等於和大於等於start和end,則將檢查有效性,然後在該節點處返回樹的值。 獲取左子值和右子值,並獲取這兩個值的LCM並返回此值。

也可以看看
House Robber II Leetcode解決方案

推薦碼  

範圍LCM查詢的C ++代碼

#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

範圍LCM查詢的Java代碼

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” 是數組中元素的數量。 該空間是存儲段樹所必需的。