ပေးထားသောအကွာအဝေးရှိ element များမှအပ array တစ်ခု၏နံပါတ်အားလုံး GCD အတွက်ရှာဖွေမှုများ  


ခက်ခဲအဆင့် ခိုင်မာသော
မကြာခဏမေးတယ် အမေဇုံ Capital One DE ရှော Google PayPal က Quora Teradata
အခင်းအကျင်း Dynamic Programming GCD သင်္ချာ ပြeryနာပြ.နာ

ပြProbleနာဖော်ပြချက်  

“ ပေးထားသောအကွာအဝေးရှိ element များမှအပ array တစ်ခု၏နံပါတ်များအားလုံး၏ GCD အတွက်ရှာဖွေမှုများ” ပြproblemနာကသင့်အားပေးလိမ့်မည်ဟုဖော်ပြသည် ကိန်း အခင်းအကျင်း နှင့်တစ်ဦး q မေးမြန်းချက်အရေအတွက်။ တစ်ခုချင်းစီကို query ကိုလက်ဝဲနှင့်ညာဘက်နံပါတ်ပါရှိသည်။ အဆိုပါပြstatementနာကြေညာချက်မေးမြန်းချက်၏ပေးထားသောအကွာအဝေးအတွင်းမှလွဲ။ အားလုံးသည်ကိန်း၏အကြီးမားဆုံးသောဘုံကွဲပြားခြင်းထွက်ရှာရန်မေးတယ်။

နမူနာ  

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

ရှင်းလင်းချက်

အညွှန်း ၂ မှ ၃ မှ element များကိုဖယ်ထုတ်သော element များ၏ GCD ဆိုလိုသည်မှာ 2 နှင့် 3 ၏ GCD သည် 1 ဖြစ်သည်

ယခုအညွှန်းကိန်းမှ ၁ ခုသို့ element များကိုဖယ်ထုတ်သော element များ၏ GCD သည် 0 နှင့် 1 ၏ GCD သည် 6 ဖြစ်သည်

နောက်တဖန်အညွှန်း ၁ မှ ၂ သို့ element များဖယ်ထုတ်ပြီးသော GCD ၏ဆိုလိုသည်မှာ 1 နှင့် 2 ၏ GCD သည် ၁ ဖြစ်သည်

ပေးထားသောအကွာအဝေးရှိ element များမှအပ array တစ်ခု၏နံပါတ်အားလုံး GCD အတွက်ရှာဖွေမှုများတွယ်အပ်

 

algorithm  

  1. ပေးထားသော input ခင်းကျင်း၏အရွယ်အစားနှင့်အရွယ်အစား Array နှစ်ခုကိုဖန်တီးပါ။
  2. 1 အညွှန်းကိန်းကနေ array ရဲ့အရှည်အထိခင်းကျင်းဖြတ်သန်းပါ။ ထို့နောက် preArray ရှိယခင် index တွင်သိမ်းဆည်းထားသောလက်ရှိ element နှင့် GCD ၏ GCD ကိုရှာပြီး preArray တွင်လက်ရှိ index တွင်သိမ်းထားပါ။
  3. ညာဘက်မှဘယ်ဘက်သို့ array ကိုဖြတ်သန်းပြီး suffixArray element ၏ GCD ကိုရှာပြီး array element နှင့် GCD ကို suffixArray တွင်သိမ်းဆည်းပါ။
  4. ပေးထားသောစုံစမ်းမှုတစ်ခုစီအတွက်ဘယ်ဘက်အကွာအဝေးသည် 0 ဖြစ်လျှင် suffixArray [right + 1] ၏တန်ဖိုးကိုပြန်ပို့ပါ။
  5. ထို့အပြင်ညာဘက်တန်ဖိုးသည် n - 1 ဖြစ်လျှင် preArray [left - 1] ၏တန်ဖိုးကိုပြန်သွားပါ။
  6. ကျန်သည် preArray [left-1] နှင့် suffixArray [right + 1] ၏ GCD တန်ဖိုးကိုပြန်ပေးပါ။
လည်းကြည့်ရှုပါ
Expression အကဲဖြတ်

ရှင်းလင်းချက်

ဖြေဆိုရန်ကိန်းနှင့်မေးမြန်းချက်များခင်းကျင်းပေးထားသည်။ ကျနော်တို့ကထွက်ရှာရန်တောင်းနေကြသည် အကြီးမြတ်ဆုံးဘုံ divisor စုံစမ်းမှု၏ပေးထားသောအကွာအဝေး၌ရှိသမျှသောကိန်းမှလွဲ။ နံပါတ်များ၏။ အကယ်၍ ကျွန်ုပ်တို့သည်အရှည် ၅ မှခင်းကျင်းထားသော ၀ မှ ၁ အထိအကွာအဝေးကိုပေးထားပါကဆိုလိုသည်မှာကျွန်ုပ်တို့သည်ကိန်းတန်းများမှ arr [0] နှင့် arr [1] မှလွဲ၍ အားလုံးသောကိန်းများ၏အကြီးမြတ်ဆုံးဘုံကွဲပြားခြင်းကိုရှာဖွေရန်ဖြစ်သည်။ ဘယ်ဘက်နဲ့ညာဘက်အကွာအဝေးအတိုင်းအတာပါဝင်တဲ့ query ။ ဒီအကွာအဝေးမှာရှိတဲ့ကိန်းပြည့်တွေကိုထားခဲ့ရမယ်။

ကျွန်ုပ်တို့သည် array ကိုဖြတ်သန်းသွားမည်ဖြစ်သော်လည်း၎င်းမတိုင်မီပေးထားသည့်ခင်းကျင်းမှု၏ပထမဆုံး element ကို preArray ၏ပထမဆုံး element ထဲသို့ကော်ပီကူးပါ။ ကြောင်းပြီးနောက်လက်ဝဲမှညာဘက်ခင်းကျင်းဖြတ်သန်း။ ဤအချိန်အတောအတွင်းကျွန်ုပ်တို့သည် preArray နှင့် suffixArray ကိုတည်ဆောက်လိမ့်မည်။ preArray အတွက်မူလအညွှန်းကိန်း၏လက်ရှိအညွှန်းကိန်းများနှင့် preArray ရှိယခင်အညွှန်းတွင် element ၏အကြီးမြတ်ဆုံးအဖြစ်များသည့် Divisor ကိုရှာဖွေပါ။ ဤနံပါတ်များကိုဤ GCD ကို preArray element တွင်သိမ်းထားပါ။ array ၏ဖြတ်သန်းပြီးနောက် suffixArray ကိုတည်ဆောက်ပါ။ ၎င်းအတွက် suffixArray ၏နောက်ဆုံး element ၏နေရာတွင်ဖြစ်သည်။ ပေးထားသော array element ၏ array ၏နောက်ဆုံး element ကိုကူးယူပါ။ ထိုနောက်မှကျွန်ုပ်တို့သည် preArray ကိုလိုက်နာသော်လည်းတူညီသောလုပ်ထုံးလုပ်နည်းကိုလိုက်နာပါ။ သို့သော်ညာဘက်မှဘယ်ဖက်သို့။

ပေးထားသောအကွာအဝေး၏ပေးထားသောစုံစမ်းမှုတစ်ခုချင်းစီအတွက်ပေးထားသောဘယ်ဘက်အကွာအဝေးသည် 0 လားမှန်မမှန်စစ်ဆေးပါ။ suffixArray [right + 1] ၏တန်ဖိုးကိုပြန်ပို့ပါ။ ညာဘက်တန်ဖိုးသည် array ၏အရှည်နှင့်မတူကိုစစ်ဆေးပါ။ ထိုအခါ preArray ၏တန်ဖိုးကိုပြန်ပို့ပါ။ ကျန်သည် preArray ရှိ left index တွင် element ၏အကြီးမားဆုံးဘုံကွဲပြားမှုကိုဖြစ်စေ၊ suffixArray ရှိ right index တွင် element ကိုပြန်ပို့ပါ။ ဒါကငါတို့လိုအပ်သောအဖြေဖြစ်လိမ့်မည်။

လည်းကြည့်ရှုပါ
အဆုံးရောက်ရှိရန်ခုန်နိမ့်ဆုံးအရေအတွက်

ကုဒ်  

ပေးထားသောအကွာအဝေးမှလွဲ။ array 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 ရှာဖွေရန်အတွက် Java code

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

ရှုပ်ထွေးဆန်းစစ်ခြင်း  

အချိန်ရှုပ်ထွေး

အို (N + Qlogn) ဘယ်မှာ "မေး" မေးမြန်းချက်အရေအတွက်နှင့်N"ဟုအဆိုပါ input ကိုခင်းကျင်းထဲမှာဒြပ်စင်များ၏နံပါတ်ဖြစ်ပါတယ်။ အို (N) preArray နှင့် suffixArray တည်ဆောက်ခြင်းအတွက်လိုအပ်သောအချိန်လိုအပ်သည်။ ထိုအခါ အို (Qlog n) မေးခွန်းများဖြေဆိုရန်အချိန်လိုအပ်သည်၊ အဘယ်ကြောင့်ဆိုသော်အဖြေတစ်ခုစီအတွက်ကျွန်ုပ်တို့သည် gcd နံပါတ်နှစ်ခုကိုရှာသောကြောင့်ကျွန်ုပ်တို့အတွက်ကုန်ကျသည်။ n သည်နံပါတ်နှင့် log သည် ၂ ကိုအခြေခံသည်။

လည်းကြည့်ရှုပါ
အဆင့် ၁၊ ၂ သို့မဟုတ် ၃ ကို သုံး၍ nth stair သို့ရောက်ရန်နည်းလမ်းများကိုရေတွက်ပါ

အာကာသရှုပ်ထွေးမှု

သတ်မှတ်ထားသောအကွာအဝေးရှိဒြပ်စင်မှအပ array တစ်ခု၏နံပါတ်များအားလုံး၏ GCD အတွက် Query များအတွက်ဖြေရှင်းရန်နေရာရှုပ်ထွေးသည် အို (N) ဘယ်မှာ "N" preArray နှင့် suffixArray ကိုသိုလှောင်ရန်အတွက် array အတွင်းရှိ element အရေအတွက်ဖြစ်သည်။