LCM မေးမြန်းမှုများ


ခက်ခဲအဆင့် ခိုင်မာသော
မကြာခဏမေးတယ် အမေဇုံ နေခြည် Google တကယ်ပါပဲ PayPal က Snapdeal Uber
အခင်းအကျင်း ပြeryနာပြ.နာ အပိုင်း - သစ်ပင် သစ်ပင်

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

ပြangeနာ“ Range LCM Queries” တွင်သင်၌ရှိကြောင်းဖော်ပြထားသည် ကိန်း အခင်းအကျင်း နှင့် q မေးမြန်းချက်အရေအတွက်။ တစ်ခုချင်းစီကို query ကို (လက်ဝဲ, လက်ယာ) အကွာအဝေးအဖြစ်ပါရှိသည်။ ပေးထားသောလုပ်ငန်းသည် 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) အတွက် LCM 6,9,10 နှင့် 8 သည် 360 ဖြစ်သည်

နောက်တစ်ကြိမ် ထပ်မံ၍ (3,7) ဖြစ်သော LCM 9,10,8,7 နှင့် 5 သည် 2520 ဖြစ်သည်

နောက်ဆုံးတွင် (5,8) LCM အတွက် 8,7,5 နှင့် 14 သည် 280 ဖြစ်လိမ့်မည်

LCM မေးမြန်းမှုများ

 

algorithm

  1. နှစ်ခုကြေညာပါ Array များ.
  2. Build a segment သစ်ပင် လက်ဝဲကလေးနှင့်လက်ျာကလေးအဘို့အလုပ်ဆောင်ချက်များကို recursurs ခေါ်ဆိုခြင်းအားဖြင့်။
  3. ဘယ်ဘက်ကလေး node နှင့်ညာဘက်ကလေး node အတွက် LCM ကိုရယူပါ။
  4. နံပါတ်တစ်ခု၏ LCM ကိုရရှိရန်ဘယ်ဘက်ကလေးနှင့်ညာကလေး၏ထုတ်ကုန်ကို GCD ဖြင့်ဝေပါ။
  5. မေးမြန်းချက်တစ်ခုစီ၏ဘယ်ဘက်နှင့်ညာဘက်ရှိအကွာအဝေးသည်မမှန်သည်ကိုစစ်ဆေးပြီးနောက် ၁ ကိုပြန်ပို့ပါ။ ဘယ်ဘက်သည် node ၏စတင်တန်ဖိုးထက်နည်းသည်ကိုမှန်မမှန်စစ်ဆေးပြီးညာဘက်သည်အဆုံးသတ် node ၏တန်ဖိုးထက်ကြီးလား၊ သစ်ပင်၏လက်ရှိတန်ဖိုးကို node ကို။
  6. အထက်ဖော်ပြပါအခြေအနေများသည်မမှန်ပါက၊ ကျန်ရှိသော node lcm နှင့် right node lcm ကိုရယူရန် function ကိုခေါ်။ LCM ရရန် lcm function ကိုခေါ်ပါ။

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

integer ခင်းကျင်းခြင်းနှင့်ဘယ်နှင့်ညာအကွာအဝေးနှင့်ပတ်သက်သောစုံစမ်းမှုအချို့ပေးထားသည်။ ရှာပါ LCM အားလုံးပါဝင်နိုင်အကွာအဝေးအတွင်းအားလုံးနံပါတ်များ။ lcm ကိုရှာဖွေရန်ပုံသေနည်းကို LC ၏ arr [left, left + 1, ……။ , right-1, right] အဖြစ်အကောင်အထည်ဖော်သည်။ သို့သော်ဤတွင်သစ်ပင်ကိုအသုံးပြုလိမ့်မည်။ ကျနော်တို့က segment ကိုသစ်ပင်တည်ဆောက်ရန်သွားကြသည်။ Array တွင်တန်ဖိုးတစ်ခုတည်းရှိသလားဆိုတာကိုစစ်ဆေးပြီးထိုအပင်၏ node ထဲသို့ထည့်ပါ။ အခြားတစ်ခုအနေဖြင့်ကျွန်ုပ်တို့သည် array ကိုတစ်ဝက်ပိုင်းခွဲပြီးဘယ်ဘက်ကလေး node အတွက်သစ်ပင်ကိုစတင်တည်ဆောက်မည်။ ထိုအခါတန်ဖိုးများကိုဘယ်ဘက် node အတွက် 2 * node နှင့်လက်ျာကလေး node + 2 * node + 1 ကို ဖြတ်၍ getLCM function သို့ ဖြတ်၍ ထိုတန်ဖိုး၏ LCM ကိုရယူပါ။ ထို node နှစ်ခုနှင့် LCM ကိုရယူပါ။ ထိုသစ်ပင်၏ node အနေအထားတွင်တန်ဖိုးကိုပြန်ပေးသည့်စတိုးဆိုင်။

LCM function တွင်၊ ဘယ်နှင့်ညာ node တန်ဖိုးများ၏အကြီးမားဆုံးဘုံစားသုံးသူကိုရှာလိမ့်မည်။ ထိုအခါကျွန်ုပ်တို့သည်ဘယ်ဘက်နှင့်ညာ node များ၏ထုတ်ကုန်နှင့်ဘယ်ဘက်နှင့်ညာ node ၏အကြီးမားဆုံးဘုံကွဲပြားခြင်း၏ထုတ်ကုန်၏ထုတ်ကုန်ပြန်လာပါလိမ့်မယ်။

query တစ်ခုစီအတွက်ဘယ်ဘက်နှင့်ညာအနေအထားအတိုင်းရရှိပါလိမ့်မည်။ အဆုံးတန်ဖိုးသည်ဘယ်ဘက်ထက်နည်းလျှင်၊ start value သည်ထက်ကြီးလျှင်၊ return ပြန်လျှင် 1 သည်မှားသောမေးခွန်းဖြစ်သည်။ ကျန်သည်၊ မှန်ကန်ခြင်းကိုဘယ်ဘက်နှင့်ညာဘက်ညီမျှမှုရှိခြင်းနှင့်ညီမျှသည်ထက်အသီးသီးစတင်ခြင်းနှင့်အဆုံးသတ်ခြင်းနှင့်ညီမျှခြင်းရှိမရှိစစ်ဆေးမှုကိုစစ်ဆေးပြီး node ရှိသစ်ပင်၏တန်ဖိုးကိုပြန်ပို့ပါလိမ့်မည်။ ဘယ်ဘက်ကလေးတန်ဖိုးနှင့်မှန်ကန်သောကလေးတန်ဖိုးကိုရယူပါ။ ၎င်းတန်ဖိုးနှစ်ခုမှ LCM ကိုယူပြီးဤတန်ဖိုးကိုပြန်ယူပါ။

ကုဒ်

Range LCM Query များအတွက် C ++ code

#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 Queries များအတွက် Java code

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

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

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

 အို (Log N * Log n) ဘယ်မှာ "N" သည် array အတွင်းရှိ element အရေအတွက်ဖြစ်သည်။ အခြား log n အဆိုပါ LCM ရှာဖွေတာများအတွက်လိုအပ်သောအချိန်ကိုဆိုလိုသည်။ ဤအချိန်ရှုပ်ထွေးမှုတစ်ခုချင်းစီကိုစုံစမ်းမှုအဘို့ဖြစ်၏။ စုစုပေါင်းအချိန်ရှုပ်ထွေးသည် အို (N + Q * Log N * log n) အဘယ်ကြောင့်ဆိုသော်အို (N) သည်သစ်ပင်ကိုတည်ဆောက်ရန်နှင့်မေးမြန်းချက်များကိုဖြေဆိုရန်အချိန်လိုအပ်သောကြောင့်ဖြစ်သည်။

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

 အို (N) ဘယ်မှာ "N" သည် array အတွင်းရှိ element အရေအတွက်ဖြစ်သည်။ ဤသည်နေရာသည် segment သစ်ပင်သိုလှောင်ရန်လိုအပ်သည်။