रेंज एलसीएम क्वेरी


कठिनाई स्तर कठिन
में अक्सर पूछा वीरांगना डायरेक्टी गूगल वास्तव में पेपैल स्नैपडील Uber
ऐरे क्वेरी की समस्या खंड-वृक्ष पेड़

समस्या का विवरण

समस्या "रेंज एलसीएम क्वेरी" कहती है कि आपके पास ए पूर्णांक सरणी और 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 का LCM और 5 है

और 5,8 और 8,7,5 के LCM (14) के लिए अंत में 280 होगा

रेंज एलसीएम क्वेरी

 

कलन विधि

  1. दो की घोषणा सरणियों.
  2. एक निर्माण खंड का पेड़ बाएं बच्चे और दाएं बच्चे के लिए कार्यों को पुन: कॉल करके।
  3. बाएं बच्चे के नोड और दाएं बच्चे के नोड के लिए एलसीएम प्राप्त करें।
  4. एक नंबर का LCM प्राप्त करने के लिए, बाएं बच्चे और दाएं बच्चे के उत्पाद को उनके GCD द्वारा विभाजित करें।
  5. बाएं और दाएं के रूप में प्रत्येक क्वेरी के लिए, जांचें कि यदि रेंज मान्य नहीं है, तो 1 वापस करें, अन्यथा जांचें कि क्या बाएं नोड के शुरुआती मूल्य से कम है और दाएं समाप्ति नोड के मूल्य से अधिक है, तो वापस लौटें पेड़ का वर्तमान मूल्य नोड।
  6. यदि उपरोक्त शर्तों में से कोई भी सत्य नहीं है, तो बाईं ओर नोड lcm और दाएँ नोड lcm प्राप्त करने के लिए पुन: फ़ंक्शन को कॉल करें और फिर इन संख्याओं के LCM प्राप्त करने के लिए lcm फ़ंक्शन को कॉल करें।

व्याख्या

पूर्णांक सरणी और बाईं और दाईं सीमा के साथ कुछ क्वेरी दी गई है। पता लगाओ एलसीएम समावेशी सीमा के भीतर सभी संख्याएँ। पता लगाने के लिए कि एलसीएम गिरफ्तारी के एलसीएम [बाएं, बाएं + 1, ……।, दाएं -1, दाएं] के रूप में फार्मूला लागू करता है, लेकिन इसमें हम एक पेड़ का उपयोग करेंगे। हम एक सेगमेंट ट्री बनाने जा रहे हैं। हम जाँचेंगे कि क्या किसी सरणी में केवल एक मान है, फिर उस विशेष मान को पेड़ के नोड में डालें। एल्स, हम सरणी को आधे में विभाजित करने और बाएं बच्चे के नोड के लिए पेड़ का निर्माण शुरू करने जा रहे हैं। फिर मानों को बाएं नोड के लिए 2 * नोड के रूप में पास करें, और दाएं बच्चे के नोड के लिए, 2 * नोड + 1 और इन वैल्यू के एलसीएम को गेटएलसीएम फ़ंक्शन में पास करके प्राप्त करें। और इन दो बच्चे नोड्स के एलसीएम प्राप्त करें और स्टोर करें जो पेड़ की नोड स्थिति में मूल्य लौटाते हैं।

LCM फ़ंक्शन में, हम उस बाएँ और दाएँ नोड मान का सबसे बड़ा सामान्य विभाजक खोजने जा रहे हैं। फिर हम बाएं और दाएं नोड्स के उत्पाद के विभाजन का उत्पाद वापस करेंगे और बाएं और दाएं नोड का सबसे बड़ा सामान्य विभाजक।

प्रत्येक क्वेरी के लिए हमें बाईं और दाईं स्थिति के रूप में मिलेगा, हम रेंज की वैधता की दोबारा जांच करेंगे यदि अंतिम मान बाईं से कम है या प्रारंभ मान दाएं से अधिक है, तो 1 वापस करें, यह एक अमान्य प्रश्न है। एल्स, हम वैधता की जांच करेंगे यदि बाएं और दाएं क्रमशः शुरू और अंत के बराबर कम और बराबर हैं, तो नोड पर पेड़ के मूल्य को वापस करें। बाएं बच्चे के मूल्य और दाएं बच्चे के मूल्य को प्राप्त करें और इन दो मूल्यों के एलसीएम प्राप्त करें और इस मूल्य को वापस करें।

कोड

रेंज 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

रेंज एलसीएम क्वेरी के लिए जावा कोड

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 (लॉग एन * लॉग एन) जहां "एन" सरणी में तत्वों की संख्या है। अन्य लॉग एन एलसीएम खोजने के लिए आवश्यक समय को दर्शाता है। यह समय जटिलता प्रत्येक प्रश्न के लिए है। कुल समय जटिलता है ओ (एन + क्यू * लॉग एन * लॉग एन), इसका कारण यह है कि पेड़ बनाने और फिर प्रश्नों का उत्तर देने के लिए O (N) समय की आवश्यकता होती है।

अंतरिक्ष जटिलता

 पर) जहां "एन" सरणी में तत्वों की संख्या है। सेगमेंट ट्री को स्टोर करने के लिए यह स्थान आवश्यक है।