د ورکړل شویو سلسلو کې د عناصرو په شمول د صف د ټولو شمیرو GCD لپاره پوښتنې


مشکل کچه سخت
په مکرر ډول دننه پوښتل کیږي ترلاسه کړئ Amazon پلازمیینه يو DE شا د ګوګل وی.دا Quora Teradata
پیشه متحرک برنامې GCD ریاضی د پوښتنې ستونزه

ستونزه بیان

"د ورکړل شوي سلسلې عناصرو پرته د ټولو لړۍ د GCD لپاره پوښتنې" ستونزې بیانوي چې تاسو ته به درکړل شي ضمیمه سور او د q د پوښتنو شمیره. هرې پوښتنې کې کی left او ښیې شمیره شامله ده. د ستونزې بیان غوښتنه کوي ترڅو د پوښتنې په ورکړل شوي حد کې دننه پرته د ټولو انټرجونو ترټولو لوی عام تقسیم کونکی ومومئ.

بېلګه

arr[] = {1, 3, 6, 9}
Query: {(2, 3), (0, 1), (1, 2)}
1 3 1

تشریح

د اجزاو GCD د 2 څخه تر 3 پورې د عناصرو استثنا د مثال په توګه ، د 1 او 3 GCD 1 دی

اوس د شاخصونو څخه تر 0 پورې د عناصرو ایستلو د عناصرو GCD د مثال په توګه ، د 1 او 6 GCD 9 دی

بیا د 1 څخه تر 2 پورې د عناصرو ایستلو د عناصرو GCD لکه د 1 او 9 GCD 1 دی

د ورکړل شویو سلسلو کې د عناصرو په شمول د صف د ټولو شمیرو GCD لپاره پوښتنې

 

الګوریتم

  1. د ورکړل شوې آخذې بrayې سره ورته دوه اندازې اندازې جوړه کړئ.
  2. د سري له 1 شاخص څخه د تیر اوږدوالي ته واچوئ. بیا د پخواني عنصر او عنصر GCD ومومئ په PreArray کې په پخوانۍ شاخص کې ساتل شوی او دا په PreArray کې اوسني شاخص کې ذخیره کړئ.
  3. له صف څخه ښیې څخه کی left ته ځیر کړئ ، او د لاسي AA د عنصر GCD او ورکړل شوی سرې عنصر ومومئ او GCD په افشا کې وسپارئ.
  4. د هرې ورکړل شوې پوښتنې لپاره ، که چیرې کی rangeې لړۍ د 0 سره مساوي وي ، نو د فرامیک اریز ارزښت [حق + 1] بیرته ورکړئ.
  5. نور که د ښیې ارزښت د n - 1 سره مساوي وي ، نو د PreArray ارزښت بیرته ورکړئ [بائیں - 1].
  6. نور د PreArray [کی--1] د GCD او ضمیمه ارای [ښیې + 1] ارزښت G بیرته ورکوي.

تشریح

د ځواب ویلو لپاره ځیرمو او پوښتنو ته ورکړل شوي. موږ څخه غوښتنه وشوه چې ومومئ ترټولو لوی عام تقویم د پوښتنو ورکړل شوي حدود کې د ټولو عددونو لپاره د شمېرو څخه. که چیرې موږ ته د 0 څخه تر 1 پورې قطار کې راکړ شي. پدې معنی چې موږ باید په یو صف کې د تیر [5] او آرر [0] څخه پرته د ټولو مسایلو ترټولو لوی عام تقویم ومومو. ورکړل شوې پوښتنه چې د اندازې په توګه کی. او ښیې لري. موږ باید عدد پریږدو چې پدې لړ کې راځي.

موږ د صف تیرول روان یو مګر د دې څخه دمخه د ورکړل شوي صف لومړي عنصر د پری آرري لومړي عنصر کې کاپي کړئ. له دې وروسته صف ته له کی from څخه ښیې ته تلو. د دې وخت په جریان کې به موږ د پری ارای او لایق اری رامینځته کړو. د PreArray لپاره په اصلي شاخص کې د عناصر خورا لوی عام تقسیم کونکی په اوسني انډیکس سر کې او په عنصر کې په تیرو شاخص کې په عنصر کې PreArray ومومئ. د دې شمېرو GCD د پری آرري عنصر کې وساتئ. د صف له ټیټیدو وروسته ، ارامیک جوړ کړئ. د دې لپاره ، د افق آریا وروستي عنصر په ځای کې. د ورکړل شوي صف عنصر د آرني وروستی عنصر کاپي کړئ. بیا وروسته ورته پروسیجر تعقیب کړئ لکه څنګه چې موږ د PreArray لپاره تعقیب کوو مګر د صف څخه ښیې څخه د سرنی.

د ورکړل شوې درجې هرې ورکړل شوې پوښتنې لپاره ، وګورئ چې ورکړل شوې کی rangeې اندازه له 0 سره مسله ده که نه نو پدې توګه د ضمیمې ارزښت اعداد [حق + 1]. وګوره چې د ښي ارزښت د صف له طول سره مساوي دی که نه. بیا د پری اری ارزښت [بائیں -1] ته بیرته ورکړئ. نور په پری انډراي کې د کی index لړلیک کې د عنصر ترټولو لوی عام تقویم او په فرعي ارای کې ښي شاخص کې عنصر راستنوي. دا به زموږ اړین ځواب وي.

کوډ

د ورکړل شوې اندازې څخه علاوه د صف د GCD موندلو لپاره C ++ کوډ

#include<iostream>

using namespace std;
int __GCD(int a, int b)
{
    if (b == 0)
        return a;

    return __GCD(b, a % b);
}

void buildArrayOfGCD(int PreArray[], int arr[], int suffixArray[], int n)
{
    PreArray[0] = arr[0];
    for (int i=1 ; i<n; i++)
        PreArray[i] = __GCD(PreArray[i-1], arr[i]);

    suffixArray[n-1] = arr[n-1];

    for (int i=n-2; i>=0 ; i--)
        suffixArray[i] = __GCD(suffixArray[i+1], arr[i]);
}

int getGCDInRange(int l, int r, int PreArray[], int suffixArray[], int n)
{
    if (l==0)
        return suffixArray[r+1];

    if (r==n-1)
        return PreArray[l-1];
    return __GCD(PreArray[l-1], suffixArray[r+1]);
}

int main()
{
    int arr[] = {1, 3, 6, 9};
    int n = sizeof(arr)/sizeof(arr[0]);
    int PreArray[n], suffixArray[n];
    buildArrayOfGCD(PreArray, arr, suffixArray, n);

    int l = 2, r = 3;
    cout << getGCDInRange(l, r, PreArray, suffixArray, n)
         << endl;
    l = 0 ;
    r = 1;
    cout << getGCDInRange(l, r, PreArray, suffixArray, n)
         << endl;
    l = 1 ;
    r = 2;
    cout << getGCDInRange(l, r, PreArray, suffixArray, n)
         << endl;
    return 0;
}
1
3
1

د ورکړل شوي حد څخه پرته د صف د GCD موندلو لپاره جاوا کوډ

import java.util.*;

class GCDNumbers
{
    static int GCD(int a, int b)
    {
        if (b == 0)
            return a;

        return GCD(b, a % b);
    }
    
    static void buildArrayOfGCD(int preArray[],int arr[], int suffixArray[], int n)
    {
        preArray[0] = arr[0];

        for (int i = 1; i < n; i++)
            preArray[i] = GCD(preArray[i - 1], arr[i]);

        suffixArray[n - 1] = arr[n - 1];

        for (int i = n - 2; i >= 0; i--)
            suffixArray[i] = GCD(suffixArray[i + 1], arr[i]);
    }

    static int getGCDInRange(int l, int r, int preArray[], int suffixArray[], int n)
    {

        if (l == 0)
            return suffixArray[r + 1];

        if (r == n - 1)
            return preArray[l - 1];

        return GCD(preArray[l - 1], suffixArray[r + 1]);
    }
    
    public static void main(String[] args)
    {
        int arr[] = { 1, 3, 6, 9};
        int n = arr.length;
        int preArray[] = new int[n];
        int suffixArray[] = new int[n];
        buildArrayOfGCD(preArray, arr, suffixArray, n);

        int l = 2, r = 3;
        System.out.println(getGCDInRange(l, r, preArray, suffixArray, n));

        l = 0;
        r = 1;
        System.out.println(getGCDInRange
                           (l, r, preArray, suffixArray, n));

        l = 1;
        r = 2;
        System.out.println(getGCDInRange
                           (l, r, preArray, suffixArray, n));
    }
}
1
3
1

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

د وخت پیچلتیا

O (N + Qlogn) هلته "Q" د پوښتنو شمیره ده او "N"د ننوت صف کې د عناصرو شمیر دی. O (N) د پری اری او لاډیر اری جوړولو لپاره وخت اړین دی. بیا O (Qlog n) پوښتنو ته د ځواب ویلو لپاره وخت اړین دی ځکه چې د هرې پوښتنې د ځواب لپاره موږ د دوه شمیرو gcd پیدا کوو چې موږ ته د نګ قیمت کوي چیرې چې n شمیره ده او لاګ د 2 اساس سره دی.

د ځای پیچلتیا

د یو لړ ټولو شمیرو GCD لپاره د پوښتنو حل کولو لپاره د ځای پیچلتیا پرته په ورکړل شوي سلسله کې عناصر O (N) هلته "N" د مخکینۍ او ضمیمې آری ذخیره کولو لپاره په صف کې د عناصرو شمیر دی.