Range LCM հարցումներ


Դժվարության մակարդակ Դժվար
Հաճախակի հարցնում են Amazon Դիրեկտի Google Իսկապես PayPal Snapdeal Uber
Դասավորություն Հարցման խնդիր Հատված-ծառ ծառ

Խնդիրի հայտարարություն

«Range LCM հարցումներ» խնդրում նշվում է, որ դուք ունեք ան ամբողջ թիվ դասավորություն և 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-ի LCM- ի համար (8) 360-ն է

Այժմ կրկին հաջորդ հարցման համար, այսինքն ՝ (3,7), 9,10,8,7 և 5-ի LCM- ն 2520 է

և վերջապես (5,8) LCM- ի համար 8,7,5 և 14-ը կկազմի 280

Range LCM հարցումներ

 

Ալգորիթմ

  1. Հայտարարեք դրանցից երկուսը զանգվածներ.
  2. Կառուցել ա հատված ծառ ձախ և աջ երեխայի գործառույթները ռեկուրսիվ կանչելով:
  3. Ձեռք բերեք LCM ձախ մանկական հանգույցի և աջ երեխայի հանգույցի համար:
  4. Թվի LCM ստանալու համար բաժանեք ձախ երեխայի և աջ երեխայի արտադրանքը նրանց GCD- ով:
  5. Ձախ և աջ հարցումների համար ստուգեք ՝ արդյոք տիրույթը վավեր չէ, ապա վերադարձրեք 1, հակառակ դեպքում ստուգեք ՝ ձախը պակաս է հանգույցի մեկնարկային արժեքից, իսկ աջը ՝ վերջավոր հանգույցի արժեքից մեծ, ապա վերադարձեք ծառի ընթացիկ արժեքի հանգույցը:
  6. Եթե ​​վերոհիշյալ պայմաններից որևէ մեկը ճիշտ չէ, այլապես ռեկուրսիվորեն զանգահարեք ֆունկցիան ՝ ձախ հանգույցի lcm և աջ հանգույց lcm ստանալու համար, ապա զանգահարեք lcm գործառույթ ՝ այս թվերի LCM ստանալու համար:

բացատրություն

Հաշվի առնելով ամբողջ զանգվածը և ձախ և աջ տիրույթով որոշ հարցում: Պարզեք LCM ընդգրկույթում ներառված բոլոր թվերի ներառյալ: Որպեսզի պարզենք, որ lcm- ն իրականացնում է բանաձևը որպես arr LCM [ձախ, ձախ + 1, ……., Աջ -1, աջ], բայց դրանում մենք ծառ ենք օգտագործելու: Մենք կառուցելու ենք հատված ծառ: Մենք ստուգելու ենք, թե զանգվածում կա միայն մեկ արժեք, այնուհետև այդ հատուկ արժեքը տեղադրում ենք ծառի հանգույցում: Այլապես, մենք պատրաստվում ենք զանգվածը բաժանել երկու մասի և սկսել կառուցել ծառը ՝ ձախ երեխայի հանգույցի համար: Դրանից հետո արժեքները փոխանցեք որպես 2 * հանգույց ձախ հանգույցի համար, իսկ աջ մանկական հանգույցի համար ՝ 2 * հանգույց + 1 և ստացեք այս արժեքի LCM ՝ այն փոխանցելով getLCM գործառույթին: Եվ ստացեք այս երկու մանկական հանգույցների LCM- ը և պահեք այդ վերադարձված արժեքը ծառի հանգույցի դիրքում:

LCM գործառույթում մենք կգտնենք այդ ձախ և աջ հանգույցների արժեքների ամենամեծ ընդհանուր բաժանարարը: Դրանից հետո մենք կվերադարձնենք ձախ և աջ հանգույցների արտադրանքի բաժանման արդյունքը և ձախ և աջ հանգույցների ամենամեծ ընդհանուր բաժանարարը:

Յուրաքանչյուր հարցման համար մենք կստանանք որպես ձախ և աջ դիրք, մենք կրկնակի ստուգելու ենք տիրույթի վավերությունը, եթե վերջի արժեքը ձախից պակաս է կամ մեկնարկի արժեքն ավելի մեծ է, քան աջը, ապա վերադարձնենք 1-ը, դա անվավեր հարց է: Այլապես, մենք ստուգելու ենք վավերականությունը, եթե ձախ և աջը համապատասխանաբար պակաս հավասար են և հավասար են համապատասխանաբար սկզբին և ավարտին, ապա վերադարձնենք ծառի արժեքը հանգույցում: Ստացեք ձախ երեխայի արժեքը և ճիշտ երեխայի արժեքը և ստացեք այս երկու արժեքների LCM և վերադարձրեք այս արժեքը:

Կոդ

C ++ կոդը Range 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

Range LCM հարցումների Java- ի կոդ

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

Բարդության վերլուծություն

Timeամանակի բարդություն

 O (Մատյան N * Մուտք n) որտեղ «Ն» զանգվածում տարրերի քանակն է: Մյուսը գրանցում n նշանակում է LCM գտնելու համար անհրաժեշտ ժամանակը: Այս ժամանակի բարդությունը յուրաքանչյուր հարցման համար է: Timeամանակի ընդհանուր բարդությունն է O (N + Q * Log N * log n), սա այն պատճառով, որ ծառը կառուցելու համար պահանջվում է O (N) ժամանակ, այնուհետև հարցումները պատասխանելու համար:

Տիեզերական բարդություն

 ՎՐԱ) որտեղ «Ն» զանգվածում տարրերի քանակն է: Այս տարածքը պահանջվում է հատված ծառը պահելու համար: