တစ်ခုခင်းကျင်းအတွက်ပ္ပံ၏ထုတ်ကုန်


ခက်ခဲအဆင့် ခိုင်မာသော
မကြာခဏမေးတယ် Accolite DE Shaw FreeCharge Google SAP Labs Snapdeal Times ကိုအင်တာနက်
အခင်းအကျင်း modular ဂဏန်းသင်္ချာ ပြeryနာပြ.နာ

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

ပြ “နာ“ Products of range in array” ကသင်၏နံပါတ်များသည် ၁ မှ n အထိ၊ မေးသောမေးနံပါတ်များပါ ၀ င်သည့်ကိန်းဂဏန်းများကိုဖော်ပြသည်။ တစ်ခုချင်းစီကိုစုံစမ်းမှုအကွာအဝေးပါရှိသည်။ အဆိုပါပြproblemနာကိုကြေညာချက် m ကိုမဆိုချုပ်နံပါတ်သည်အဘယ်မှာရှိ modulo M အောက်မှာပေးထားသောအကွာအဝေးအတွင်းထုတ်ကုန်ထွက်ရှာရန်မေးတယ်။

နမူနာ

arr[] = {1,2,3,4,5,6}

M = 131

Query = [1, 6], [2, 4]
65 24

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

modulo ကိုအသုံးပြုသည့်အခါ ၁ မှ ၆ အထိ ၇၂၀ နှုန်းဖြင့်ထုတ်လုပ်ထားပြီး ၆၅ နှင့် ၂၄ ကျန်သည်။

တစ်ခုခင်းကျင်းအတွက်ပ္ပံ၏ထုတ်ကုန်

ချဉ်းကပ်နည်း

နံပါတ်တစ်ခုကိုကန ဦး နံပါတ်နှင့်အဆုံးသတ်အဖြစ်သတ်မှတ်သည် ဂဏန်း။ ဒီအကွာအဝေးကိုထည့်သွင်းတွက်ချက်ရာတွင် In-between နံပါတ်များအားလုံးနှင့်ပြည့်နေသည်။ ကျွန်ုပ်တို့၏တာဝန်မှာဒီအကွာအဝေးအတွင်းနံပါတ်များထုတ်ကုန်ကိုရှာဖွေရန်ဖြစ်သည်။ ကုန်ပစ္စည်းနှင့်ပြောင်းပြန်ထုတ်ကုန်ကိုကျွန်ုပ်တို့တွက်ချက်မည်။ ထို့နောက်၊ ကျွန်ုပ်တို့သည်စုံစမ်းမှုကိုဖြေရှင်းလိမ့်မည်။ ဤအဆင့်တွင်ကုန်ပစ္စည်း pre-product နှင့် inverse product တွက်ချက်မှုအဆင့်နှစ်ဆင့်၊ တစ်ကြိမ်ချင်းမေးမြန်းမှုပေါင်းများစွာကိုဖြေရှင်းလိမ့်မည်။ t သည်စုံစမ်းမှုတစ်ခုကိုဖြေရှင်းရန် algorithm တစ်ခုလုံးကိုဖြတ်ကျော်ရန်လိုသည်။

ပထမ ဦး စွာ array ၏ pre-product ကိုတွက်ချက်ပါ။ ဆိုလိုသည်မှာကျွန်ုပ်တို့သည် array ကိုဖြတ်သန်းရမည်ဖြစ်ပြီး၊ ပထမတစ်ခုအနေဖြင့်၊ ပေးထားသော array ၏ပထမ element ကို pre-product array ၏ပထမဆုံး element သို့ကူးယူရန်လိုအပ်သည်။ ကျွန်ုပ်တို့သည်ခင်းကျင်းပေးထားသောခင်းကျင်း၏ပထမနေရာမှ array ကိုဖြတ်သန်းသွားပြီး၊ ပေးထားသောခင်းကျင်းခြင်းနှင့်ထုတ်ကုန်ခင်းကျင်းခြင်း၏ယခင်ဒြပ်စင်၏ထုတ်ကုန်ကိုသိမ်းဆည်းလိမ့်မည်။ modulo ကိုထိန်းသိမ်းရန်ကျွန်ုပ်တို့၏ရရှိသောထုတ်ကုန်၏ modulo ကိုသိုလှောင်လိမ့်မည်။ ပြီးတော့ product array ထဲမှာသိမ်းထားပါ။

နောက်တစ်ဆင့်တွင်ကျွန်ုပ်တို့သည်ပြောင်းပြန်ထုတ်ကုန်ကိုတွက်ချက်ပါမည်။ ဆိုလိုသည်မှာကျွန်ုပ်တို့သည်အကွာအဝေး၏ပြောင်းပြန်ထုတ်ကုန်ကိုဆိုလိုခြင်းဖြစ်သည်။ ဤသို့ဆိုလျှင်ကျွန်ုပ်တို့သည်ပြောင်းပြန်ထုတ်ကုန်ကို i index အညွှန်းအထိမတွက်လျှင်၊ ပြောင်းပြန်ထုတ်ကုန်သည်နံပါတ်အားလုံး၏ထုတ်ကုန်ဖြစ်လိမ့်မည်။ အကွာအဝေးကနေဈမှ။ ဤနည်းဖြင့်ကျွန်ုပ်တို့သည်ရှာဖွေမှုကိုစဉ်ဆက်မပြတ်ဖြေရှင်းနိုင်သည်။ စုံစမ်းမှုတစ်ခုစီအတွက်အပိုထပ်ဆောင်းကြိုးပမ်းရန်မလိုအပ်ပါ။ ယခုကျွန်ုပ်တို့သည် query ကိုဖြေရှင်းလျှင် PreProduct [right] နှင့် PreInverseProduct [left-0] ၏ထုတ်ကုန်ကိုသာပြန်ပို့ရမည်။ ဤသည်လိုအပ်သောအဖြေဖြစ်လိမ့်မည်။

ကုဒ်

Products of range of array ကိုရှာရန် C ++ code

#include <iostream>
using namespace std;
#define MAX 100

int PreProductArray[MAX];
int PreInverseProduct[MAX];

int InverseP(int a, int modulo)
{
    int mP = modulo, temp, quotient;
    int xP = 0, x = 1;

    if (modulo == 1)
        return 0;

    while (a > 1)
    {
        quotient = a / modulo;

        temp = modulo;

        modulo = a % modulo;
        a = temp;

        temp = xP;

        xP = x - quotient * xP;

        x = temp;
    }
    if (x < 0)
        x += mP;

    return x;
}

void calculatePreProduct(int A[], int N, int P)
{
    PreProductArray[0] = A[0];

    for (int i = 1; i < N; i++)
    {
        PreProductArray[i] = PreProductArray[i - 1] *A[i];

        PreProductArray[i] = PreProductArray[i] % P;
    }
}
void calculatePreInverseProduct(int A[], int N, int P)
{
    PreInverseProduct[0] = InverseP(PreProductArray[0], P);

    for (int i = 1; i < N; i++)
        PreInverseProduct[i] = InverseP(PreProductArray[i], P);
}
int calculateProduct(int A[], int L, int R, int P)
{
    L = L - 1;
    R = R - 1;
    int ans;

    if (L == 0)
        ans = PreProductArray[R];
    else
        ans = PreProductArray[R] *
              PreInverseProduct[L - 1];

    return ans;
}

int main()
{
    int Arr[] = { 1, 2, 3, 4, 5, 6 };

    int N = sizeof(Arr) / sizeof(Arr[0]);

    int Modulo = 131;
    calculatePreProduct(Arr, N, Modulo);
    calculatePreInverseProduct(Arr, N, Modulo);

    int Left = 1, Right = 6;
    cout << calculateProduct(Arr, Left, Right, Modulo) << endl;

    Left = 2, Right = 4;
    cout << calculateProduct(Arr, Left, Right, Modulo)
         << endl;
    return 0;
}
65
24

ကုန်ပစ္စည်းများကို array ထဲမှာရှာရန် Java code

class ProductInRange
{

    static int MAX = 100;
    static int PreProductArray[] = new int[MAX];
    static int PreInverseProduct[] = new int[MAX];

    static int InverseP(int a, int modulo)
    {
        int mP = modulo, temp, quotient;
        int xP = 0, x = 1;

        if (modulo == 1)
            return 0;

        while (a > 1)
        {
            quotient = a / modulo;

            temp = modulo;

            modulo = a % modulo;
            a = temp;

            temp = xP;

            xP = x - quotient * xP;

            x = temp;
        }
        if (x < 0)
            x += mP;

        return x;
    }
    
    static void calculatePreProduct(int A[], int N, int P)
    {
        PreProductArray[0] = A[0];

        for (int i = 1; i < N; i++)
        {
            PreProductArray[i] = PreProductArray[i - 1] *
                                 A[i];
            PreProductArray[i] = PreProductArray[i] % P;
        }
    }
    
    static void calculatePreInverseProduct(int A[], int N, int P)
    {
        PreInverseProduct[0] = InverseP(PreProductArray[0], P);

        for (int i = 1; i < N; i++)
            PreInverseProduct[i] = InverseP(PreProductArray[i],
                                            P);
    }
    
    static int calculateProduct(int A[], int L, int R, int P)
    {
        L = L - 1;
        R = R - 1;
        int ans;

        if (L == 0)
            ans = PreProductArray[R];
        else
            ans = PreProductArray[R] *
                  PreInverseProduct[L - 1];

        return ans;
    }
    
    public static void main(String[] args)
    {

        int Arr[] = { 1, 2, 3, 4, 5, 6 };

        int Modulo = 131;
        calculatePreProduct(Arr, Arr.length, Modulo);
        calculatePreInverseProduct(Arr, Arr.length,
                                   Modulo);
        int Left = 1, Right = 6;
        System.out.println(calculateProduct(Arr, Left,
                                            Right, Modulo));
        Left = 2;
        Right = 4;
        System.out.println(calculateProduct(Arr, Left,
                                            Right, Modulo));

    }
}
65
24

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

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

အို (N + M + Q log) ဒီမှာ M ကထုတ်ကုန်များအတွက်ပြောင်းပြန်ရှာတွေ့၏ကြောင့် log ။ ထို့နောက်မေးခွန်းများဖြေဆိုရန် O (Q) ။

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

အို (N) ဘယ်မှာ "N" သည် array အတွင်းရှိ element အရေအတွက်ဖြစ်သည်။ ငါတို့သိမ်းထားတဲ့ကြောင့် ကြိုတင်ထုတ်လုပ်မှု နှင့် နေပြည်တော် Array များ။