ഒരു ശ്രേണിയിലെ ശ്രേണികളുടെ ഉൽപ്പന്നങ്ങൾ


വൈഷമ്യ നില ഹാർഡ്
പതിവായി ചോദിക്കുന്നു അക്കോലൈറ്റ് ഡി.ഇ.ഷാ ഫ്രീചാർജ് ഗൂഗിൾ എസ്എപി ലാബുകൾ സ്നാപ്ഡേൽ ടൈംസ് ഇന്റർനെറ്റ്
അറേ മോഡുലാർ അരിത്മെറ്റിക് അന്വേഷണ പ്രശ്നം

പ്രശ്നം പ്രസ്താവന

“ഒരു ശ്രേണിയിലെ ശ്രേണികളുടെ ഉൽ‌പ്പന്നങ്ങൾ‌” എന്ന പ്രശ്‌നം, നിങ്ങൾക്ക് 1 മുതൽ n വരെയുള്ള സംഖ്യകളും q ചോദ്യങ്ങളുടെ എണ്ണം സംഖ്യകളും അടങ്ങുന്ന ഒരു സംഖ്യ അറേ നൽകിയിട്ടുണ്ടെന്ന് പറയുന്നു. ഓരോ ചോദ്യത്തിലും ശ്രേണി അടങ്ങിയിരിക്കുന്നു. M എന്നത് ഏതെങ്കിലും പ്രൈം നമ്പറായ മൊഡ്യൂളോ M ന് കീഴിൽ തന്നിരിക്കുന്ന പരിധിക്കുള്ളിൽ ഉൽപ്പന്നം കണ്ടെത്താൻ പ്രശ്‌ന പ്രസ്താവന ആവശ്യപ്പെടുന്നു.

ഉദാഹരണം

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

M = 131

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

വിശദീകരണം 

1 മുതൽ 6 വരെ, മോഡുലോ പ്രയോഗിക്കുമ്പോൾ ശ്രേണിയുടെ ഉൽ‌പ്പന്നം 720 ആണ്, അത് 65 ഉപേക്ഷിക്കുകയും 24 എണ്ണം അതേപടി തുടരുകയും ചെയ്യുന്നു.

ഒരു ശ്രേണിയിലെ ശ്രേണികളുടെ ഉൽപ്പന്നങ്ങൾ

സമീപനം

ഒരു സംഖ്യയുടെ ശ്രേണി ഒരു ആരംഭ സംഖ്യയായും അവസാനമായും നൽകി അക്കം. ഈ ശ്രേണി പരിഗണിക്കുന്നത്, അതിനിടയിലുള്ള എല്ലാ അക്കങ്ങളും നിറഞ്ഞതാണ്. ഈ ശ്രേണിയിലെ അക്ക സംഖ്യകളുടെ ഉൽ‌പ്പന്നം കണ്ടെത്തുക എന്നതാണ് ഞങ്ങളുടെ ചുമതല. ഞങ്ങൾ ഉൽ‌പ്പന്നവും വിപരീത ഉൽ‌പ്പന്നവും കണക്കാക്കും, പിന്നീട്, ഞങ്ങൾ‌ അന്വേഷണം പരിഹരിക്കും, ഇതോടെ, പ്രീ-പ്രൊഡക്റ്റ്, വിപരീത ഉൽ‌പ്പന്നം എന്നിവ കണക്കാക്കുന്നതിനുള്ള രണ്ട് ഘട്ടങ്ങൾ‌, ഞങ്ങൾ‌ ഒരു സമയം ഒന്നിലധികം ചോദ്യങ്ങൾ‌ പരിഹരിക്കും, ഞങ്ങൾ‌ ചെയ്യരുത് ' ഒരു ചോദ്യം പരിഹരിക്കുന്നതിന് മുഴുവൻ അൽ‌ഗോരിതം കൂടി പോകേണ്ടതില്ല.

ആദ്യം, അറേയുടെ പ്രീ-പ്രൊഡക്റ്റ് കണക്കാക്കുക, അതായത്, ഞങ്ങൾ അറേയിലൂടെ സഞ്ചരിക്കണം, ഒന്നാമതായി, തന്നിരിക്കുന്ന അറേയുടെ ആദ്യ ഘടകം പ്രീ-പ്രൊഡക്റ്റ് അറേയുടെ ആദ്യ ഘടകത്തിലേക്ക് പകർത്തേണ്ടതുണ്ട്. തന്നിരിക്കുന്ന അറേയുടെ ആദ്യ സ്ഥാനത്ത് നിന്ന് ഞങ്ങൾ അറേയിലൂടെ സഞ്ചരിക്കുകയും തന്നിരിക്കുന്ന അറേയുടെ മുൻ ഘടകത്തിന്റെയും ഉൽപ്പന്ന അറേയുടെയും ഉൽപ്പന്നം സംഭരിക്കുകയും ചെയ്യും, മൊഡ്യൂൾ നിലനിർത്തുന്നതിന്, നമുക്ക് ലഭിക്കുന്ന ഉൽപ്പന്നത്തിന്റെ മൊഡ്യൂൾ ഞങ്ങൾ സംഭരിക്കും ഉൽപ്പന്ന അറേയിൽ സംഭരിക്കുക.

അടുത്ത ഘട്ടത്തിൽ, ഞങ്ങൾ വിപരീത ഉൽ‌പ്പന്നം കണക്കാക്കും, ഇതിനൊപ്പം, ശ്രേണിയുടെ വിപരീത ഉൽ‌പ്പന്നമാണ് ഞങ്ങൾ അർത്ഥമാക്കുന്നത്, അതായത് വിപരീത ഉൽ‌പ്പന്നം ith സൂചിക വരെ കണക്കാക്കുകയാണെങ്കിൽ, വിപരീത ഉൽ‌പ്പന്നം എല്ലാ അക്കങ്ങളുടെയും ഉൽ‌പ്പന്നമായിരിക്കും 0 മുതൽ i വരെയുള്ള ശ്രേണി. ഇതുപയോഗിച്ച്, ചോദ്യം നിരന്തരമായ സമയത്ത് ഞങ്ങൾക്ക് പരിഹരിക്കാൻ കഴിയും. ഓരോ ചോദ്യവും പരിഹരിക്കുന്നതിന് ഞങ്ങൾ കൂടുതൽ ശ്രമിക്കേണ്ടതില്ല. ഇപ്പോൾ പരിഹരിക്കാനുള്ള അന്വേഷണം ലഭിക്കുകയാണെങ്കിൽ ഞങ്ങൾ പ്രീപ്രൊഡക്റ്റ് [വലത്], പ്രീഇൻ‌വേർ‌സ് പ്രൊഡക്റ്റ് [ഇടത് -1] എന്നിവയുടെ ഉൽപ്പന്നം തിരികെ നൽകും. ഇത് ആവശ്യമായ ഉത്തരമായിരിക്കും.

കോഡ്

ശ്രേണിയിലെ ശ്രേണികളുടെ ഉൽപ്പന്നങ്ങൾ കണ്ടെത്തുന്നതിന് സി ++ കോഡ്

#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

ഒരു ശ്രേണിയിലെ ശ്രേണികളുടെ ഉൽപ്പന്നങ്ങൾ കണ്ടെത്താനുള്ള ജാവ കോഡ്

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

സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (N ലോഗ് M + Q), ഉൽ‌പ്പന്നത്തിനായുള്ള വിപരീതം കണ്ടെത്തിയതിനാലാണ് ഇവിടെ ലോഗ് എം. ചോദ്യങ്ങൾക്ക് ഉത്തരം നൽകുന്നതിന് O (Q).

ബഹിരാകാശ സങ്കീർണ്ണത

O (N) എവിടെ "N" അറേയിലെ ഘടകങ്ങളുടെ എണ്ണം. കാരണം ഞങ്ങൾ സംഭരിച്ചു പ്രീ പ്രൊഡക്റ്റ് ഒപ്പം preProductInverse ശ്രേണികൾ.