दायरा LCM प्रश्नहरू


कठिनाई तह हार्ड
बारम्बार सोधिन्छ अमेजन Directi गुगल वास्तवमा PayPal स्नैपडल Uber
एरे प्रश्न समस्या खण्ड-रूख ट्री

समस्या वक्तव्य

समस्या "दायरा LCM प्रश्नहरू" भन्छन् कि तपाईंसँग एक छ पूर्णांक arrayq प्रश्नहरूको संख्या। प्रत्येक क्वेरीले दायराको रूपमा (बाँया, दाँया) समावेश गर्दछ। दिइएको कार्य भनेको 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 is is० हो

अब अर्को क्वेरीका लागि फेरि, (3,7),,, १०,9,10,8,7, L र of को LCM २ 5२० हो

र अन्तमा (,,5,8) LCM 8,7,5 र १ 14 को २ 280० हुनेछ

दायरा LCM प्रश्नहरू

 

अल्गोरिदम

  1. दुई मध्ये घोषणा गर्नुहोस् एर्रेहरू.
  2. निर्माण गर्नुहोस् खण्ड रूख बायाँ बच्चाहरु र दायाँ बच्चाहरुका लागि क्रमिक रुपमा कार्यहरू बोलाउँदै।
  3. बाँया बच्चा नोड र दायाँ बच्चा नोडको लागि LCM पाउनुहोस्।
  4. नम्बरको LCM प्राप्त गर्न, बाँया बच्चा र दायाँ बच्चाको उत्पादनलाई उनीहरूको GCD द्वारा विभाजन गर्नुहोस्।
  5. बायाँ र दायाँको रूपमा प्रत्येक क्वेरीका लागि, दायरा मान्य छैन कि छैन जाँच गर्नुहोस् तब १ फिर्ता गर्नुहोस्, अन्यथा बायाँ नोडको सुरूवात मानभन्दा कम छ र दायाँ अन्त्य हुने नोडको मानभन्दा ठूलो छ कि छैन जाँच गर्नुहोस्। रूखको वर्तमान मूल्य नोड।
  6. यदि माथिको कुनै पनि अवस्था सही छैन भने अन्यथा बायाँ नोड lcm र दायाँ नोड lcm प्राप्त गर्न प्रकार्य कल गर्नुहोस् र त्यसपछि यी संख्याहरूको LCM प्राप्त गर्न lcm प्रकार्य कल गर्नुहोस्।

स्पष्टीकरण

एक पूर्णांक एरे र बायाँ र दायाँ दायराको साथ केहि प्रश्नहरू दिइयो। पत्ता लगाउनुहोस् LCM समावेशी रूपमा दायरा भित्र सबै नम्बरहरूको। Lcm पत्ता लगाउन एआरआरको LCM को रूपमा सूत्र कार्यान्वयन पत्ता लगाउन [बायाँ, बायाँ + १, ……।, दायाँ -१, दायाँ], तर यसमा हामी रूख प्रयोग गर्दैछौं। हामी खण्ड रूख निर्माण गर्न जाँदैछौं। हामी जाँच गर्नेछौं यदि कुनै एर्रेमा केवल एक मान छ भने, त्यसपछि त्यो विशेष मान रूखको नोडमा घुसाउनुहोस्। अर्को, हामी एर्रेलाई आधामा विभाजन गर्दै जान्छौं र बायाँ बच्चाहरूको नोडका लागि रूखको निर्माण सुरु गर्नेछौं त्यसपछि बायाँ नोडको लागि २ * नोडको रूपमा मानहरू, र दायाँ बच्चा नोडका लागि, २ * नोड + १ पास गर्नुहोस् र getLCM प्रकार्यमा यसलाई पार गरेर यी मानहरूको LCM पाउनुहोस्। र यी दुई बच्चा नोडहरूको LCM पाउनुहोस् र रूखको नोड स्थितिमा मान फर्काउँछ।

LCM प्रकार्यमा, हामी त्यो बायाँ र दायाँ नोड मानहरूको सब भन्दा ठूलो साधारण भाजक भेट्टाउने छौं। त्यसो भए हामी बायाँ र दायाँ नोडहरूको उत्पादनको डिभिजनको उत्पादन र बायाँ र दायाँ नोडको सबैभन्दा ठूलो साधारण भाजक फिर्ता गर्नेछौं।

प्रत्येक क्वेरीको लागि हामी बाँया र दायाँ स्थितिको रूपमा प्राप्त गर्नेछौं, हामी दायराको वैधता डबल-जाँच गर्नेछौं यदि अन्त्य मान बायाँ भन्दा कम छ वा सुरूवात मान दाँया भन्दा ठूलो छ, तब १ फिर्ता गर्नुहोस्, यो एक अवैध प्रश्न हो। अन्यथा, हामी वैधता जाँच गर्नेछौं यदि बायाँ र दायाँ क्रमशः सुरु र अन्त्यमा बराबर भन्दा बराबर छ भने नोडमा रूखको मान फिर्ता गर्नेछौं। बाँया बच्चा मूल्य र दायाँ बच्चा मान प्राप्त गर्नुहोस् र यी दुई मानहरूको 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

दायरा 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

जटिलता विश्लेषण

समय जटिलता

 हे (लग एन * लग एन) जहाँ "N" एर्रेमा एलिमेन्ट्सको संख्या हो। अन्य लग एन LCM खोज्नको लागि आवश्यक समय दर्शाउँछ। यो समय जटिलता प्रत्येक क्वेरीको लागि हो। कुल समय जटिलता हो ओ (एन + क्यू * लग एन * लग एन), यो किनकि O (N) समय आवश्यक छ रूख बनाउन र त्यसपछि प्रश्नहरूको उत्तर दिन।

ठाउँ जटिलता

 O (N) जहाँ "N" एर्रेमा एलिमेन्ट्सको संख्या हो। खण्ड रूखको भण्डारको लागि यो ठाउँ आवाश्यक हुन्छ।