Տրված ինդեքսի GCD- ները զանգվածում են


Դժվարության մակարդակ Դժվար
Հաճախակի հարցնում են ԴԵ Շոուն PayPal Snapchat Snapdeal Times ինտերնետ Քսոմե
Դասավորություն Հարցման խնդիր Հատված-ծառ ծառ

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

«Տրված ինդեքսի տողերի GCD- ները զանգվածում» խնդրի մեջ նշվում է, որ ձեզ տրված է ամբողջ թիվ դասավորություն և տեսականու որոշ հարցումներ: Խնդրի հայտարարությունը խնդրում է պարզել տիրույթում այդքան ձևավորված ենթախմբի ամենամեծ ընդհանուր բաժանարարը:

Օրինակ

arr[] = {10, 5, 18, 9, 24}
Query: {(0, 1), (2, 4), (0, 3)}
5 3 1

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

Առաջին հարցման ամենամեծ ընդհանուր բաժանարարը տատանվում է 0-ի և 1-ի միջև, ուստի 10-ի և 5-ի GCD- ն 5 է:

Երկրորդ հարցման GCD- ն տատանվում է 2-ի և 4-ի միջև, ուստի 18, 9, 24-ի GCD- ն 3 է:

Առաջին հարցման ամենամեծ ընդհանուր բաժանարարը տատանվում է 0-ի և 3-ի միջև, ուստի GCD- ն 1 է:

Տրված ինդեքսի GCD- ները զանգվածում են

 

Ալգորիթմ

  1. Սկսեք arr [0] arr [n-1] հատվածի հատվածից և շարունակեք բաժանել հավասար մասերի: Ամեն անգամ ընթացիկ հատվածը բաժանում ենք հավասար մասերի: Հետո կրկնակի զանգահարեք երկու մասի: Եվ յուրաքանչյուր նման հատվածի համար մենք բաժանում ենք ամենամեծ ընդհանուր բաժանարար արժեքը հատված ծառի մեջ:
  2. Կառուցեք հատված ծառ, որը կլրացվի վերջին մակարդակից մի կողմ:
  3. Հատված ծառի յուրաքանչյուր հանգույց պահպանում է որոշակի տիրույթին համապատասխանող բոլոր տարրերի GCD- ն:
  4. GCD- ի հարցումը պարզելու համար, եթե հանգույցի տիրույթը կլինի startQuery- ում և endQuery- ում, ապա արժեքը վերադարձրեք հանգույցում:
  5. Այլապես, եթե միջակայքը վավեր չէ, ապա վերադարձրու՛ք null- ը կամ -1:
  6. Այլապես վերադարձեք GCD գործառույթի ռեկուրսիվ զանգը:

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

Մեզ տրված է ամբողջ թիվ դասավորություն և q հարցումների քանակը: Յուրաքանչյուր հարցում պարունակում է ընդգրկույթը որպես startQuery և endQuery: Այս միջակայքում մենք պետք է պարզենք տրված տիրույթը բավարարող բոլոր թվերի ամենամեծ ընդհանուր բաժանարարը: Դրա համար մենք պատրաստվում ենք կառուցել հատված ծառ, մենք հարցումները կլուծենք տեղեկամատյան N * log n- ի արդյունավետ ժամանակում:

Մենք կսկսենք կառուցել հատված ծառը զանգվածի 0-րդ դիրքից մինչ զանգվածի վերջին դիրքը, և կարևոր մասը զանգվածը բաժանելն է երկու մասի: Մենք կշարունակենք բաժանել այն այնքան ժամանակ, քանի դեռ զանգվածի երկարությունը չի լինի մեկ, այնուհետև հաջորդ քայլում հետադարձաբար կանչենք գործառույթը զանգվածի երկու մասերին: Այստեղ մենք պահելու ենք ամենամեծ ընդհանուր բաժանարարը ծառի հանգույցում: Բոլոր ներքին հանգույցները զրոյական չեն լինի, բացառությամբ տերևի հանգույցների: Այսպիսով կազմված ծառը կլինի երկուական ծառ: Քանի որ յուրաքանչյուր հանգույցի մակարդակում զանգվածի երկու մաս կա: Բայց համեմատած երկուական ծառի հետ, որտեղ հանգույցները մեկ թվի փոխարեն ներկայացնում են մի տիրույթ:

Տված Ամենամեծ ընդհանուր բաժանարարի յուրաքանչյուր հարցման համար մենք ստուգում ենք, արդյոք հանգույցի տիրույթը գտնվում է startQuery- ի և endQuery- ի սահմաններում: Դրանից հետո մենք արժեքը կվերադարձնենք հատված ծառի հանգույցում: Մենք ունենք նաև երկրորդ պայմանը, եթե եթե հանգույցի միջակայքը դուրս է տիրույթի startQuery տիրույթից և endQuery տիրույթից: Դրանից հետո մենք կվերադարձնենք -1 կամ զրոյական արժեք: Եվ ֆունկցիան շարունակաբար առաջադեմ դարձնելու համար մենք ռեկուրսիվորեն կանվանենք հանգույցի և՛ երեխային, և՛ ձախ, և՛ աջ: Դրանից հետո պարզեք հանգույցներից վերադարձված արժեքի ամենամեծ ընդհանուր բաժանարարը:

Կոդ

C ++ կոդ ՝ զանգվածի մեջ տրված ինդեքսային տիրույթների GCD գտնելու համար

#include<iostream>
#include<math.h>

using namespace std;

int *segTree;

int gcd(int a, int b)
{
    if (a < b)
    {
        int temp = b;
        b = a;
        a = temp;
    }

    if (b==0)
        return a;
    return gcd(b,a%b);
}

int getGCDOfNumber(int startNode, int endNode, int startQuery, int endQuery, int si)
{
    if (startNode>endQuery || endNode < startQuery)
        return 0;
    if (startQuery<=startNode && endQuery>=endNode)
        return segTree[si];

    int mid = startNode+(endNode-startNode)/2;

    return gcd(getGCDOfNumber(startNode, mid, startQuery, endQuery, si*2+1),
               getGCDOfNumber(mid+1, endNode, startQuery, endQuery, si*2+2));
}

int findRangeGcd(int startNode, int endNode, int arr[],int n)
{
    if (startNode<0 || endNode > n-1 || startNode>endNode)
    {
        cout << "Invalid Arguments" << "\n";
        return -1;
    }
    return getGCDOfNumber(0, n-1, startNode, endNode, 0);
}

int buildSegementTree(int arr[], int startNode, int endNode, int si)
{
    if (startNode==endNode)
    {
        segTree[si] = arr[startNode];
        return segTree[si];
    }
    int mid = startNode+(endNode-startNode)/2;

    segTree[si] = gcd(buildSegementTree(arr, startNode, mid, si*2+1),
                      buildSegementTree(arr, mid+1, endNode, si*2+2));
    return segTree[si];
}

int *constructendNodegmentTree(int arr[], int n)
{
    int height = (int)(ceil(log2(n)));
    int size = 2*(int)pow(2, height)-1;
    segTree = new int[size];
    buildSegementTree(arr, 0, n-1, 0);
    return segTree;
}

int main()
{
    int a[] = {10, 5, 18, 9, 24};
    int n = sizeof(a)/sizeof(a[0]);

    constructendNodegmentTree(a, n);

    int l = 0, r = 1;
    cout << "Greatest Common Divisor is: ";
    cout << findRangeGcd(l, r, a, n) << "\n";

    l = 2;
    r = 4;
    cout << "Greatest Common Divisor is: ";
    cout << findRangeGcd(l, r, a, n) << "\n";

    l = 0;
    r = 3;
    cout << "Greatest Common Divisor is: ";
    cout << findRangeGcd(l, r, a, n) << "\n";

    return 0;
}
Greatest Common Divisor is: 5
Greatest Common Divisor is: 3
Greatest Common Divisor is: 1

Java կոդ ՝ զանգվածի մեջ տրված ինդեքսային տիրույթների GCD գտնելու համար

import java.io.*;

public class GCDOfNumber
{
    private static int[] segTree;

    public static int[] buildSegmentTree(int[] arr)
    {
        int height = (int)Math.ceil(Math.log(arr.length)/Math.log(2));
        int size = 2*(int)Math.pow(2, height)-1;
        segTree = new int[size];
        SegementTree(arr, 0, arr.length-1, 0);

        return segTree;
    }

    public static int SegementTree(int[] arr, int startNode,
                                   int endNode, int si)
    {
        if (startNode==endNode)
        {
            segTree[si] = arr[startNode];

            return segTree[si];
        }
        int mid = startNode+(endNode-startNode)/2;

        segTree[si] = gcd(SegementTree(arr, startNode, mid, si*2+1),
                          SegementTree(arr, mid+1, endNode, si*2+2));
        return segTree[si];
    }

    private static int gcd(int a, int b)
    {
        if (a < b)
        {
            int temp = b;
            b = a;
            a = temp;
        }

        if (b==0)
            return a;
        return gcd(b,a%b);
    }

    public static int findRangeGcd(int startNode, int endNode, int[] arr)
    {
        int n = arr.length;

        if (startNode<0 || endNode > n-1 || startNode>endNode)
            throw new IllegalArgumentException("Invalid arguments");

        return findGcd(0, n-1, startNode, endNode, 0);
    }

    public static int findGcd(int startNode, int endNode, int startQuery, int endQuery, int si)
    {
        if (startNode>endQuery || endNode < startQuery)
            return 0;

        if (startQuery<=startNode && endQuery>=endNode)
            return segTree[si];

        int mid = startNode+(endNode-startNode)/2;

        return gcd(findGcd(startNode, mid, startQuery, endQuery, si*2+1),
                   findGcd(mid+1, endNode, startQuery, endQuery, si*2+2));
    }

    public static void main(String[] args)throws IOException
    {
        int[] a = {10, 5, 18, 9, 24};

        buildSegmentTree(a);

        int l = 0, r = 1;
        System.out.println("Greatest Common Divisor is: "+findRangeGcd(l, r, a));

        l = 2;
        r = 4;
        System.out.println("Greatest Common Divisor is: "+findRangeGcd(l, r, a));

        l = 0;
        r = 3;
        System.out.println("Greatest Common Divisor is: "+findRangeGcd(l, r, a));
    }
}
Greatest Common Divisor is: 5
Greatest Common Divisor is: 3
Greatest Common Divisor is: 1

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

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

O (n տեղեկամատյան n + տեղեկամատյան n * տեղեկամատյան (min (a, b)))) որտեղ «Ն» հանգույցների քանակն է և «Ա» և «Բ» հանգույցներ են, որոնց GCD- ն հաշվարկվում է միաձուլման գործողության ընթացքում: O (n logn) ժամանակը ծախսվում է շինարարության համար և O (տեղեկամատյան n) յուրաքանչյուր հարցումին պատասխանելու համար, ապա O (տեղեկամատյան (min (a, b))) gcd գտնելու ժամանակը:

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

O (n) որտեղ «Ն» հանգույցներն են: Տարածքը ծախսվում է հատված ծառի կառուցման վրա: