રેંજ એલસીએમ ક્વેરીઝ


મુશ્કેલી સ્તર હાર્ડ
વારંવાર પૂછવામાં આવે છે એમેઝોન ડાયરેક્ટિ Google ખરેખર પેપાલ સ્નેપડીલ ઉબેર
અરે ક્વેરી સમસ્યા સેગમેન્ટ-ટ્રી વૃક્ષ

સમસ્યા નિવેદન

સમસ્યા "રેંજ એલસીએમ ક્વેરીઝ" જણાવે છે કે તમારી પાસે પૂર્ણાંક એરે અને 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. જો ઉપરની કોઈ પણ સ્થિતિ સાચી નથી, તો બાકીના ડાબા નોડ એલસીએમ અને જમણા નોડ એલસીએમ મેળવવા માટે ફંક્શનને ફરીથી ક callલ કરો અને પછી આ નંબરોના એલસીએમ મેળવવા માટે એલસીએમ ફંક્શનને ક .લ કરો.

સમજૂતી

પૂર્ણાંક એરે અને ડાબી અને જમણી શ્રેણી સાથેની કેટલીક ક્વેરી આપી. શોધો એલસીએમ સમાવિષ્ટ શ્રેણીમાંની તમામ સંખ્યાઓની સંખ્યા. એલસીએમ એ એઆરઆર [ડાબી, ડાબી +1, ……., જમણી -1, જમણી] ની એલસીએમ તરીકે સૂત્ર અમલીકરણ શોધવા માટે, પરંતુ આમાં, આપણે એક વૃક્ષનો ઉપયોગ કરીશું. અમે એક સેગમેન્ટ ટ્રી બનાવવાની છે. આપણે તપાસ કરીશું કે એરેમાં ફક્ત એક જ મૂલ્ય છે કે નહીં, તે પછી તે ચોક્કસ મૂલ્ય ઝાડના નોડમાં દાખલ કરીશું. બાકી, આપણે ડાબી બાળાના નોડ માટે એરેને અડધા ભાગમાં વહેંચીશું અને વૃક્ષ બનાવવાનું શરૂ કરીશું. પછી ડાબા નોડ માટે 2 * નોડ તરીકે કિંમતો પસાર કરો, અને જમણા ચાઇલ્ડ નોડ માટે, 2 * નોડ + 1 અને getLCM ફંક્શનમાં પસાર કરીને આ મૂલ્યનો LCM મેળવો. અને આ બંને ચાઇલ્ડ નોડ્સનો એલસીએમ મેળવો અને સ્ટોર જે વૃક્ષની નોડ પોઝિશન પર વળતર આપે છે.

એલસીએમ ફંક્શનમાં, અમે તે ડાબી અને જમણી નોડ કિંમતોનો સૌથી સામાન્ય સામાન્ય વિભાજક શોધીશું. પછી અમે ડાબી અને જમણી નોડ્સના ઉત્પાદનના ભાગલા અને ડાબી અને જમણી નોડના સૌથી સામાન્ય સામાન્ય વિભાજકને પાછા આપીશું.

દરેક ક્વેરી માટે આપણે ડાબી અને જમણી સ્થિતિ તરીકે મેળવીશું, જો અંતિમ મૂલ્ય ડાબી કરતા ઓછું હોય અથવા પ્રારંભિક મૂલ્ય જમણા કરતા વધારે હોય, તો આપણે શ્રેણીની માન્યતાને બે વાર ચકાસીશું, પછી 1 પરત કરો, તે અમાન્ય પ્રશ્ન છે. બાકી, જો આપણે ડાબી અને જમણી ક્રમશ and શરૂઆત અને અંતની સમાન કરતાં ઓછી બરાબર અને વધારે હોય તો માન્યતા ચકાસીશું, પછી નોડ પર ઝાડનું મૂલ્ય પાછું આપવું. ડાબું બાળક મૂલ્ય અને જમણા બાળ મૂલ્ય મેળવો અને આ બે મૂલ્યોનો એલસીએમ મેળવો અને આ મૂલ્ય પરત કરો.

કોડ

રેન્જ એલસીએમ ક્વેરીઝ માટે સી ++ કોડ

#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

જટિલતા વિશ્લેષણ

સમય જટિલતા

 ઓ (લ Nગ એન * લ nગ એન) જ્યાં “એન” એરેમાં તત્વોની સંખ્યા છે. બીજી લ nગ એન એલસીએમ શોધવા માટે જરૂરી સમય સૂચવે છે. આ સમયની જટિલતા દરેક ક્વેરી માટે છે. કુલ સમય જટિલતા છે ઓ (એન + ક્યૂ * લ Logગ એન * લ logગ એન), આ એટલા માટે છે કારણ કે ઝાડ બનાવવા અને પછી પ્રશ્નોના જવાબો માટે ઓ (એન) સમય આવશ્યક છે.

અવકાશ જટિલતા

 ઓ (એન) જ્યાં “એન” એરેમાં તત્વોની સંખ્યા છે. સેગમેન્ટ વૃક્ષને સંગ્રહિત કરવા માટે આ જગ્યા આવશ્યક છે.