ಶ್ರೇಣಿಯಲ್ಲಿನ ಶ್ರೇಣಿಗಳ ಉತ್ಪನ್ನಗಳು


ತೊಂದರೆ ಮಟ್ಟ ಹಾರ್ಡ್
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಅಕೋಲೈಟ್ ಡಿಇ ಶಾ ಫ್ರೀಚಾರ್ಜ್ ಗೂಗಲ್ ಎಸ್‌ಎಪಿ ಲ್ಯಾಬ್‌ಗಳು ಸ್ನ್ಯಾಪ್ಡಿಯಲ್ ಟೈಮ್ಸ್ ಇಂಟರ್ನೆಟ್
ಅರೇ ಮಾಡ್ಯುಲರ್ ಅಂಕಗಣಿತ ಪ್ರಶ್ನೆ ಸಮಸ್ಯೆ

ಸಮಸ್ಯೆ ಹೇಳಿಕೆ

“ಶ್ರೇಣಿಯಲ್ಲಿನ ಶ್ರೇಣಿಗಳ ಉತ್ಪನ್ನಗಳು” ಎಂಬ ಸಮಸ್ಯೆಯು ನಿಮಗೆ 1 ರಿಂದ n ಮತ್ತು q ಸಂಖ್ಯೆಯ ಪ್ರಶ್ನೆಗಳನ್ನು ಒಳಗೊಂಡಿರುವ ಸಂಖ್ಯೆಗಳನ್ನು ಒಳಗೊಂಡಿರುವ ಒಂದು ಪೂರ್ಣಾಂಕ ಶ್ರೇಣಿಯನ್ನು ನೀಡಲಾಗಿದೆ ಎಂದು ಹೇಳುತ್ತದೆ. ಪ್ರತಿಯೊಂದು ಪ್ರಶ್ನೆಯು ಶ್ರೇಣಿಯನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಸಮಸ್ಯೆಯ ಹೇಳಿಕೆಯು ಮಾಡ್ಯುಲೋ ಎಂ ಅಡಿಯಲ್ಲಿ ನಿರ್ದಿಷ್ಟ ವ್ಯಾಪ್ತಿಯಲ್ಲಿ ಉತ್ಪನ್ನವನ್ನು ಕಂಡುಹಿಡಿಯಲು ಕೇಳುತ್ತದೆ, ಅಲ್ಲಿ ಮೀ ಯಾವುದೇ ಅವಿಭಾಜ್ಯ ಸಂಖ್ಯೆ.

ಉದಾಹರಣೆ

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 (Q).

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಒ (ಎನ್) ಅಲ್ಲಿ “ಎನ್” ರಚನೆಯ ಅಂಶಗಳ ಸಂಖ್ಯೆ. ಏಕೆಂದರೆ ನಾವು ಸಂಗ್ರಹಿಸಿದ್ದೇವೆ ಪೂರ್ವ ಉತ್ಪನ್ನ ಮತ್ತು preProductInverse ಸರಣಿಗಳು.