د ورکړل شوي شاخصونو GCDs په صف کې


مشکل کچه سخت
په مکرر ډول دننه پوښتل کیږي DE شا وی.دا Snapchat سنیپډیل ټایمز انټرنیټ Xome
پیشه د پوښتنې ستونزه برخه - ونې ونې

ستونزه بیان

ستونزه د ورکړل شوي شاخصونو GCDs په صف کې "په ګوته کوي چې تاسو ته ورکړل شوي ضمیمه سور او یو څه لړ پوښتنې. د ستونزې بیان غوښتنه کوي ترڅو د فرعي سرلیکونو ترټولو لوی عام تقویم ومومي چې په حد کې رامینځته شوی.

بېلګه

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 دی.

د ورکړل شوي شاخصونو GCDs په صف کې

 

الګوریتم

  1. د برخې برخې سره پیل کړئ [0] د آرر لپاره [n-1] ، او په مساوي برخو وېشلو ته دوام ورکړئ. هرځله چې موږ موجوده برخه په مساوي برخو ویشلو. بیا په تکرار سره د دوه برخو لپاره زنګ ووهئ. او د هرې برخې لپاره ، موږ د حوزې په ونې کې ترټولو لوی عام تقسیم کونکی ارزښت ذخیره کوو.
  2. د سیګ ونې جوړه کړئ کوم چې به د وروستي کچې څخه جلا شي.
  3. د برخې ونې هر نوډ د ټاکلې اندازې پورې اړوند د ټولو عناصرو GCD ذخیره کوي.
  4. د GCD د پوښتنې موندلو لپاره ، که چیرې د نوډ سلسله په startQuery او endQuery کې وي ، نو بیا ارزښت په نوډ کې بیرته ورکړئ.
  5. که چیرې ، دا سلسله معتبره نده ، نو نوال یا -1 بیرته راستانه کړئ.
  6. نور د GCD فعالیت تکرار کال بیرته راګرځئ.

تشریح

موږ ته ورکړل شو ضمیمه سور او د پوښتنو شمیره. هرې پوښتنې د startQuery او endQuery په توګه لړۍ لري. پدې حد کې ، موږ باید د ټولو شمیرو ترټولو لوی عام تقسیم کونکی ومومو چې ورکړل شوي حد پوره کوي. د دې لپاره موږ د جوړولو کار روان یو برخه ونې ، موږ به د پوښتنې حل د N N log n په مؤثره وخت کې حل کړو.

موږ به د صف د دریم پوړ څخه د سرې وروستۍ موقعیت ته د برخې ونې په جوړولو پیل وکړو ، او مهمه برخه د صف په دوه برخو ویشل کیږي. موږ به دا تقسیم کړو تر هغه چې د سرنی اوږدوالی یو نه وي ، نو بیا به په بل ګام کې په ترتیب سره د سری دواړو برخو ته فنکشن ووایو. دلته به موږ د ونې په غوټه کې ترټولو لوی عام تقسیم کونکی وساتو. ټول داخلي نوډونه به خالي نه وي ، پرته د پا nې نوډونه. هغه جوړه شوې ونه به دوه لمبر ونه وي. ځکه چې دلته په هر نوډ کچه کې د سیر دوه برخې شتون لري. مګر د بائنری ونې سره پرتله کول ، چیرې چې نوډونه د واحد شمیرو پرځای سلسله نمایش کوي.

د ورکړل شوي عالي مشترک تفسیر هرې پوښتنې لپاره ، موږ ګورو چې د نوډ حد د startQuery او endQuery کې دی. بیا به موږ د برخې د ونې نوډ کې بیرته راستون کړو. موږ دوهم حالت هم لرو چیرې چې چیرې که د نوډ اندازه د لړۍ له پیل څخه وتلې وي. بیا به موږ -1 یا یو بې ارزښته ارزښت بیرته راولو. او د فعالیت د دوامداره پرمختګ لپاره ، موږ به په تکراري ډول د نوډ دواړه ماشوم ، کی left او ښي ته واستوو. بیا د نوډونو څخه د بیرته راستنیدونکي ارزښت ترټولو لوی عام تقسیم کونکی ومومئ.

کوډ

په صف کې د ورکړل شوي شاخصونو GCDs موندلو لپاره C ++ کوډ

#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

په صف کې د ورکړل شوي شاخصونو GCDs موندلو لپاره د جاوا کوډ

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

د پیچلتیا تحلیل

د وخت پیچلتیا

O (n log n + log n * log (min (a، b))) هلته "n" د نوډونو شمیره ده او "A" او "ب" هغه نوډونه دي چې GCD د یوځای کیدو عملیاتو په جریان کې محاسبه کیږي. O (n ننوتل) وخت د ودانولو لپاره مصرفیږي او O (log n) هرې پوښتنې ته ځواب ورکول او بیا O (نګ (دقیق (a ، b)) د gcd موندلو وخت.

د ځای پیچلتیا

اې (N) هلته "n" نوډونه دي ځای د برخې د ونې په جوړولو کې مصرفیږي.