வரம்பு LCM வினவல்கள்


சிரமம் நிலை கடின
அடிக்கடி கேட்கப்படுகிறது அமேசான் டைரக்டி கூகிள் உண்மையில் பேபால் 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 ஆக இருக்கும்

வரம்பு LCM வினவல்கள்

 

அல்காரிதம்

  1. இரண்டை அறிவிக்கவும் வரிசைகள்.
  2. ஒரு கட்ட பிரிவு மரம் இடது குழந்தை மற்றும் சரியான குழந்தைக்கான செயல்பாடுகளை மீண்டும் மீண்டும் அழைப்பதன் மூலம்.
  3. இடது குழந்தை முனை மற்றும் வலது குழந்தை முனைக்கு எல்.சி.எம் கிடைக்கும்.
  4. ஒரு எண்ணின் எல்.சி.எம் பெற, இடது குழந்தை மற்றும் வலது குழந்தையின் உற்பத்தியை அவர்களின் ஜி.சி.டி மூலம் பிரிக்கவும்.
  5. ஒவ்வொரு வினவலுக்கும் இடது மற்றும் வலது என, வரம்பு செல்லுபடியாகவில்லையா என்று சரிபார்த்து 1 ஐத் திரும்பவும், இல்லையெனில் இடது முனையின் தொடக்க மதிப்பை விடக் குறைவாகவும் வலதுபுறம் முடிவடையும் முனையின் மதிப்பை விடவும் அதிகமாக உள்ளதா என சரிபார்க்கவும். மரத்தின் தற்போதைய மதிப்பு முனை.
  6. மேலே உள்ள நிபந்தனைகளில் ஏதேனும் உண்மை இல்லையென்றால், இடது முனை எல்.சி.எம் மற்றும் வலது முனை எல்.சி.எம் பெற மீண்டும் மீண்டும் செயல்பாட்டை அழைக்கவும், பின்னர் இந்த எண்களின் எல்.சி.எம் பெற எல்.சி.எம் செயல்பாட்டை அழைக்கவும்.

விளக்கம்

ஒரு முழு வரிசை மற்றும் இடது மற்றும் வலது வரம்பில் சில வினவல்கள் கொடுக்கப்பட்டுள்ளன. கண்டுபிடிக்க LCM வரம்பில் உள்ள அனைத்து எண்களையும் உள்ளடக்கியது. எல்.சி.எம் சூத்திரத்தை எல்.சி.எம் ஆக [இடது, இடது + 1, ……., வலது -1, வலது] என செயல்படுத்துகிறது, ஆனால் இதில், நாம் ஒரு மரத்தைப் பயன்படுத்துவோம். நாங்கள் ஒரு பிரிவு மரத்தை உருவாக்கப் போகிறோம். ஒரு வரிசையில் ஒரே ஒரு மதிப்பு இருக்கிறதா என்று நாங்கள் சோதித்துப் பார்ப்போம், பின்னர் அந்த குறிப்பிட்ட மதிப்பை மரத்தின் முனையில் செருகவும். வேறு, நாங்கள் வரிசையை பாதியாகப் பிரித்து, மரத்தை உருவாக்கத் தொடங்குவோம், இடது குழந்தை முனைக்கு. மதிப்புகளை இடது முனைக்கு 2 * முனையாகவும், வலது குழந்தை முனைக்கு 2 * முனை + 1 ஆகவும், இந்த மதிப்பின் எல்.சி.எம்-ஐ கெட்.எல்.சி.எம் செயல்பாட்டிற்கு அனுப்புவதன் மூலம் பெறவும். இந்த இரண்டு குழந்தை முனைகளின் எல்.சி.எம் மற்றும் மரத்தின் முனை நிலையில் மதிப்பை வழங்கிய கடையை பெறுங்கள்.

எல்.சி.எம் செயல்பாட்டில், அந்த இடது மற்றும் வலது முனை மதிப்புகளின் மிகப் பெரிய பொதுவான வகுப்பான் கண்டுபிடிக்கப் போகிறோம். இடது மற்றும் வலது முனைகளின் உற்பத்தியின் பிரிவின் தயாரிப்பு மற்றும் இடது மற்றும் வலது முனையின் மிகப் பெரிய பொதுவான வகுப்பான்.

ஒவ்வொரு வினவலுக்கும் நாம் இடது மற்றும் வலது நிலையைப் பெறுவோம், இறுதி மதிப்பு இடதுபுறத்தை விடக் குறைவாக இருந்தால் அல்லது தொடக்க மதிப்பு வலப்பக்கத்தை விட அதிகமாக இருந்தால் வரம்பின் செல்லுபடியை இருமுறை சரிபார்க்கிறோம், பின்னர் 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

சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது

 O (பதிவு N * பதிவு n) எங்கே “என்” என்பது வரிசையில் உள்ள உறுப்புகளின் எண்ணிக்கை. மற்ற பதிவு n எல்.சி.எம் கண்டுபிடிக்க தேவையான நேரத்தை குறிக்கிறது. ஒவ்வொரு வினவலுக்கும் இந்த நேர சிக்கலானது. மொத்த நேர சிக்கலானது O (N + Q * Log N * log n), ஏனென்றால், மரத்தை உருவாக்க O (N) நேரம் தேவைப்படுகிறது, பின்னர் கேள்விகளுக்கு பதிலளிக்க வேண்டும்.

விண்வெளி சிக்கலானது

 ஓ (என்) எங்கே “என்” என்பது வரிசையில் உள்ள உறுப்புகளின் எண்ணிக்கை. பிரிவு மரத்தை சேமிக்க இந்த இடம் தேவை.