अ‍ॅरेमधील श्रेणीची उत्पादने  


अडचण पातळी हार्ड
वारंवार विचारले एकत्रित डीई शॉ फ्रीचार्ज Google एसएपी लॅब Snapdeal टाइम्स इंटरनेट
अरे मॉड्यूलर अंकगणित क्वेरी समस्या

समस्या विधान  

"अ‍ॅरेमधील श्रेणींचे उत्पादन" समस्या असे सांगते की आपणास पूर्णांक अ‍ॅरे दिलेला आहे ज्यात संख्या 1 आणि एन आणि क्यू संख्यांसह असते. प्रत्येक क्वेरीमध्ये श्रेणी असते. प्रॉब्लेम स्टेटमेंटमध्ये मोड्युलो एम अंतर्गत दिलेल्या श्रेणीतील उत्पादन शोधण्यासाठी विचारतो जिथे मी कुठलीही प्राथमिक संख्या असते.

उदाहरण  

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

M = 131

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

स्पष्टीकरण 

1 ते 6 पर्यंत, मोड्यूलो लागू केला जातो तेव्हा श्रेणीचे उत्पादन 720 असते जेव्हा ते 65 वर सोडते आणि 24 समान राहील.

अ‍ॅरेमधील श्रेणीची उत्पादने

दृष्टीकोन  

आरंभिक संख्या आणि शेवट म्हणून संख्याची श्रेणी दिली संख्या. ही श्रेणी लक्षात घेता ती सर्व इन-दरम्यानच्या संख्यांसह भरली आहे. या श्रेणीतील संख्या क्रमांकाचे उत्पादन शोधणे हे आपले कार्य आहे. आम्ही उत्पादन आणि व्यस्त उत्पादनाची गणना करत आहोत, त्यानंतर, आम्ही पूर्व-उत्पादन आणि व्यस्त उत्पादनाची गणना करण्याच्या दोन चरणांसह या क्वेरीचे निराकरण करू, आम्ही एकाच वेळी एकाधिक क्वेरींचे निराकरण करू, आम्ही डॉन ' क्वेरीचे निराकरण करण्यासाठी संपूर्ण अल्गोरिदममध्ये जाण्याची आवश्यकता नाही.

प्रथम अ‍ॅरेच्या प्री-प्रॉडक्टची गणना करा, म्हणजे आपल्याला अ‍ॅरे ओलांडणे आवश्यक आहे आणि सर्व प्रथम, आपल्याला दिलेल्या अ‍ॅरेचा पहिला घटक प्री-प्रॉडक्ट अ‍ॅरेच्या पहिल्या घटकामध्ये कॉपी करणे आवश्यक आहे. आम्ही दिलेल्या अ‍ॅरेच्या पहिल्या स्थानापासून, अ‍ॅरेला मागे टाकू आणि दिलेल्या अ‍ॅरेच्या मागील घटकाचे उत्पादन आणि अ‍ॅरे प्रोडक्ट संचयित करू, मॉड्युलो देखरेखीसाठी, आम्ही मिळवलेल्या उत्पादनाचे मॉड्यूलू संचयित करू. आणि उत्पादन अ‍ॅरेमध्ये संचयित करा.

हे सुद्धा पहा
सर्वात लांब फिबोनॅकी सबसक्वेन्सची लांबी

पुढच्या चरणात, आम्ही व्यस्त उत्पादनाची गणना करीत आहोत, यासह, आम्ही श्रेणीचे व्युत्पन्न उत्पादन याचा अर्थ घेत आहोत, जसे की जर आम्ही आयथ इंडेक्स पर्यंतच्या व्युत्पादनाची गणना केली तर व्युत्पन्न उत्पादन सर्व संख्यांचे गुणधर्म असेल श्रेणी 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

गुंतागुंत विश्लेषण  

वेळ कॉम्प्लेक्सिटी

ओ (एन लॉग एम + क्यू), येथे लॉग एम उत्पादनासाठी व्यस्त शोधण्यामुळे आहे. आणि मग प्रश्नांची उत्तरे देण्यासाठी ओ (प्र).

हे सुद्धा पहा
एकल क्रमांक

स्पेस कॉम्प्लेक्सिटी

ओ (एन) जेथे “एन” अ‍ॅरे मधील घटकांची संख्या. कारण आम्ही साठवले पूर्वउत्पादक आणि पूर्वउत्पादक उलट अ‍ॅरे.