श्रेणी एलसीएम क्वेरी


अडचण पातळी हार्ड
वारंवार विचारले ऍमेझॉन डायरेक्टि Google खरंच पोपल Snapdeal उबेर
अरे क्वेरी समस्या विभाग-वृक्ष झाड

समस्या विधान

“रेंज एलसीएम क्वेरी” ही समस्या सांगते की आपल्याकडे एक आहे पूर्णांक अॅरे आणि q क्वेरी संख्या. प्रत्येक क्वेरीमध्ये श्रेणी (डावी, उजवीकडे) असते. दिलेले कार्य म्हणजे एलसीएम (डावीकडील, उजवीकडे) म्हणजेच डाव्या आणि उजव्या श्रेणीत येणार्‍या सर्व क्रमांकाचे एलसीएम शोधणे.

उदाहरण

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 चा एलसीएम 360 आहे

आता पुन्हा पुढील क्वेरीसाठी (3,7), 9,10,8,7 आणि 5 चे एलसीएम 2520 आहे

आणि शेवटी (5,8) 8,7,5 आणि 14 चे एलसीएम 280 असेल

श्रेणी एलसीएम क्वेरी

 

अल्गोरिदम

  1. दोन घोषित करा अ‍ॅरे.
  2. बिल्ड ए विभाग वृक्ष डाव्या मुलासाठी आणि उजव्या मुलासाठी फंक्शन्सला वारंवार कॉल करून.
  3. डाव्या मुलाच्या नोडसाठी आणि उजव्या मुलाच्या नोडसाठी एलसीएम मिळवा.
  4. एका क्रमांकाचा एलसीएम मिळविण्यासाठी, डाव्या मुलाचे आणि उजव्या मुलाचे उत्पादन त्यांच्या जीसीडीने विभाजित करा.
  5. डावी आणि उजवी प्रत्येक क्वेरीसाठी, श्रेणी वैध नाही की नाही ते तपासा नंतर 1 परत करा, अन्यथा डाव्या नोडच्या सुरूवातीच्या मूल्यापेक्षा कमी आहे का आणि उजवा शेवटच्या नोडच्या मूल्यापेक्षा अधिक आहे की नाही ते तपासा, तर परत द्या. झाडाचे वर्तमान मूल्य नोड
  6. जर वरीलपैकी कोणतीही परिस्थिती सत्य नसेल तर अन्यथा डावा नोड एलसीएम व उजवा नोड एलसीएम मिळविण्यासाठी फंक्शनला पुन्हा कॉल करा आणि नंतर या क्रमांकाचे एलसीएम मिळविण्यासाठी एलसीएम फंक्शनला कॉल करा.

स्पष्टीकरण

पूर्णांक अ‍ॅरे आणि डावी आणि उजवी श्रेणीसह काही क्वेरी दिली. शोधा एलसीएम सर्व श्रेणींचा समावेश समावेश. एलआरएम सूत्रानुसार एआरआरचा डावीकडील सूत्र अंमलात आणण्यासाठी [डावे, डावे +1, ……., उजवे -1, उजवे] शोधा, परंतु यामध्ये आपण वृक्ष वापरणार आहोत. आम्ही सेगमेंट ट्री बांधणार आहोत. अ‍ॅरेमध्ये फक्त एकच मूल्य आहे का ते तपासू, तर त्या झाडाच्या नोडमध्ये ते विशिष्ट व्हॅल्यू घाला. बाकी, डाव्या मुलाच्या नोडसाठी आपण अर्धे अर्धे विभाजीत करू आणि वृक्ष बांधायला लागणार आहोत. नंतर डाव्या नोडसाठी 2 * नोड आणि उजव्या मुलाच्या नोडसाठी 2 * नोड + 1 म्हणून मूल्ये द्या आणि getLCM फंक्शनमध्ये जाऊन या मूल्याचे एलसीएम मिळवा. आणि या दोन चाइल्ड नोड्सचा एलसीएम मिळवा आणि झाडाच्या नोड पोझिशनवर परत केलेले मूल्य मिळवा.

एलसीएम फंक्शनमधे आम्ही त्या डाव्या आणि उजव्या नोड व्हॅल्यूजचा सर्वात मोठा सामान्य विभाजक शोधणार आहोत. मग आम्ही डाव्या आणि उजव्या नोड्सच्या उत्पादनाच्या भागाचे उत्पादन आणि डाव्या आणि उजव्या नोडचा सर्वात मोठा सामान्य विभाजक परत करू.

प्रत्येक क्वेरीसाठी आम्हाला डावी आणि उजवी स्थिती मिळेल, शेवटची किंमत डावीपेक्षा कमी असल्यास किंवा प्रारंभ मूल्य उजवीपेक्षा जास्त असल्यास आम्ही श्रेणीची वैधता पुन्हा तपासू, नंतर 1 परत द्या, हा एक अवैध प्रश्न आहे. अन्यथा, डावी व उजवीकडील सुरूवातीस आणि शेवटी अनुक्रमेपेक्षा कमी व त्यापेक्षा कमी असल्यास वैधता तपासू, नंतर नोडवर झाडाचे मूल्य परत द्या. डावे मूल मूल्य आणि योग्य मुलाचे मूल्य मिळवा आणि या दोन मूल्यांचे एलसीएम मिळवा आणि हे मूल्य परत करा.

कोड

श्रेणी एलसीएम क्वेरींसाठी सी ++ कोड

#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

श्रेणी एलसीएम क्वेरींसाठी जावा कोड

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

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

 ओ (लॉग एन * लॉग एन) जेथे “एन” अ‍ॅरे मधील घटकांची संख्या. इतर लॉग एन एलसीएम शोधण्यासाठी लागणारा वेळ दर्शवितो. यावेळी प्रत्येक क्वेरीसाठी गुंतागुंत आहे. एकूण वेळ जटिलता आहे ओ (एन + क्यू * लॉग एन * लॉग एन), कारण वृक्ष बांधायला आणि नंतर प्रश्नांची उत्तरे द्यायला ओ (एन) वेळ आवश्यक आहे.

स्पेस कॉम्प्लेक्सिटी

 ओ (एन) जेथे “एन” अ‍ॅरे मधील घटकांची संख्या. सेगमेंट वृक्ष साठवण्यासाठी ही जागा आवश्यक आहे.