ਇੱਕ ਐਰੇ ਵਿੱਚ ਰੇਂਜ ਦੇ ਉਤਪਾਦ


ਮੁਸ਼ਕਲ ਪੱਧਰ ਹਾਰਡ
ਅਕਸਰ ਪੁੱਛਿਆ ਜਾਂਦਾ ਹੈ ਇਕੱਤਰ ਡੀਈ ਸ਼ਾ ਫ੍ਰੀਚਾਰਜ ਗੂਗਲ SAP ਲੈਬਜ਼ Snapdeal ਟਾਈਮਜ਼ ਇੰਟਰਨੈੱਟ
ਅਰੇ ਮਾਡਯੂਲਰ ਗਣਿਤ ਪ੍ਰਸ਼ਨ ਸਮੱਸਿਆ

ਸਮੱਸਿਆ ਦਾ ਬਿਆਨ

ਸਮੱਸਿਆ "ਐਰੇ ਵਿੱਚ ਰੇਂਜ ਦੇ ਉਤਪਾਦ" ਕਹਿੰਦੀ ਹੈ ਕਿ ਤੁਹਾਨੂੰ ਪੂਰਨ ਅੰਕ ਦਿੱਤਾ ਜਾਂਦਾ ਹੈ ਜਿਸ ਵਿੱਚ ਨੰਬਰ 1 ਤੋਂ ਲੈ ਕੇ ਐਨ ਅਤੇ ਕਿ q ਨੰਬਰ ਦੇ ਹੁੰਦੇ ਹਨ. ਹਰੇਕ ਪੁੱਛਗਿੱਛ ਵਿੱਚ ਸੀਮਾ ਹੁੰਦੀ ਹੈ. ਸਮੱਸਿਆ ਦਾ ਬਿਆਨ ਮੋਡੀulਲੋ ਐਮ ਦੇ ਅਧੀਨ ਦਿੱਤੀ ਗਈ ਸੀਮਾ ਦੇ ਅੰਦਰ ਉਤਪਾਦ ਦਾ ਪਤਾ ਲਗਾਉਣ ਲਈ ਕਹਿੰਦਾ ਹੈ ਜਿਥੇ ਕਿ m ਕੋਈ ਪ੍ਰਮੁੱਖ ਨੰਬਰ ਹੁੰਦਾ ਹੈ.

ਉਦਾਹਰਨ

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

M = 131

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

ਕਥਾ 

1 ਤੋਂ 6 ਤੱਕ, ਰੇਂਜ ਦਾ ਉਤਪਾਦ 720 ਹੁੰਦਾ ਹੈ ਜਦੋਂ ਮੋਡੂਲੋ ਲਾਗੂ ਕੀਤਾ ਜਾਂਦਾ ਹੈ ਤਾਂ ਇਹ 65 ਛੱਡ ਜਾਂਦਾ ਹੈ ਅਤੇ 24 ਇਕੋ ਜਿਹੇ ਰਹਿੰਦੇ ਹਨ.

ਇੱਕ ਐਰੇ ਵਿੱਚ ਰੇਂਜ ਦੇ ਉਤਪਾਦ

ਪਹੁੰਚ

ਇੱਕ ਸ਼ੁਰੂਆਤੀ ਨੰਬਰ ਅਤੇ ਅੰਤ ਦੇ ਰੂਪ ਵਿੱਚ ਇੱਕ ਸੰਖਿਆ ਦੀ ਇੱਕ ਸੀਮਾ ਦਿੱਤੀ ਗਈ ਗਿਣਤੀ. ਇਸ ਸੀਮਾ ਤੇ ਵਿਚਾਰ ਕਰਨਾ ਕਿਉਂਕਿ ਇਹ ਸਾਰੇ ਅੰਦਰੂਨੀ ਸੰਖਿਆਵਾਂ ਨਾਲ ਭਰਿਆ ਹੋਇਆ ਹੈ. ਸਾਡਾ ਕੰਮ ਇਸ ਸੀਮਾ ਦੇ ਅੰਦਰ ਨੰਬਰਾਂ ਦੇ ਉਤਪਾਦਾਂ ਦਾ ਪਤਾ ਲਗਾਉਣਾ ਹੈ. ਅਸੀਂ ਉਤਪਾਦ ਅਤੇ ਵਿਪਰੀਤ ਉਤਪਾਦਾਂ ਦੀ ਗਣਨਾ ਕਰਾਂਗੇ, ਫਿਰ, ਬਾਅਦ ਵਿਚ, ਅਸੀਂ ਪੁੱਛਗਿੱਛ ਨੂੰ ਹੱਲ ਕਰਾਂਗੇ, ਇਸ ਨਾਲ, ਪੂਰਵ-ਉਤਪਾਦ ਅਤੇ ਉਲਟਾ ਉਤਪਾਦ ਦੀ ਗਣਨਾ ਕਰਨ ਦੇ ਦੋ ਕਦਮ, ਅਸੀਂ ਇਕ ਸਮੇਂ ਵਿਚ ਕਈ ਪ੍ਰਸ਼ਨਾਂ ਨੂੰ ਹੱਲ ਕਰਾਂਗੇ, ਅਸੀਂ ਨਹੀਂ ਕਰਦੇ '. ਟੀ ਨੂੰ ਹੱਲ ਕਰਨ ਲਈ ਪੂਰੇ ਐਲਗੋਰਿਦਮ ਵਿਚ ਜਾਣ ਦੀ ਜ਼ਰੂਰਤ ਹੈ.

ਪਹਿਲਾਂ ਐਰੇ ਦੇ ਪ੍ਰੀ-ਪ੍ਰੋਡਕਟ ਦੀ ਗਣਨਾ ਕਰੋ, ਯਾਨੀ ਸਾਨੂੰ ਐਰੇ ਨੂੰ ਪਾਰ ਕਰਨਾ ਹੈ ਅਤੇ ਸਭ ਤੋਂ ਪਹਿਲਾਂ, ਸਾਨੂੰ ਦਿੱਤੇ ਐਰੇ ਦੇ ਪਹਿਲੇ ਐਲੀਮੈਂਟ ਨੂੰ ਪ੍ਰੀ-ਪ੍ਰੋਡਕਟ ਐਰੇ ਦੇ ਪਹਿਲੇ ਐਲੀਮੈਂਟ ਵਿਚ ਕਾਪੀ ਕਰਨ ਦੀ ਜ਼ਰੂਰਤ ਹੈ. ਅਸੀਂ ਦਿੱਤੀ ਐਰੇ ਦੀ ਪਹਿਲੀ ਸਥਿਤੀ ਤੋਂ, ਐਰੇ ਨੂੰ ਪਾਰ ਕਰਾਂਗੇ, ਅਤੇ ਦਿੱਤੇ ਗਏ ਐਰੇ ਦੇ ਪਿਛਲੇ ਐਲੀਮੈਂਟ ਦੇ ਉਤਪਾਦ ਅਤੇ ਉਤਪਾਦ ਐਰੇ ਨੂੰ ਸਟੋਰ ਕਰਾਂਗੇ, ਮਾਡਿoਲੋ ਨੂੰ ਬਣਾਈ ਰੱਖਣ ਲਈ, ਅਸੀਂ ਜੋ ਉਤਪਾਦ ਪ੍ਰਾਪਤ ਕਰਦੇ ਹਾਂ ਉਸ ਦੇ ਮਾਡਿoਲੋ ਨੂੰ ਸਟੋਰ ਕਰਾਂਗੇ. ਅਤੇ ਇਸ ਨੂੰ ਉਤਪਾਦ ਐਰੇ ਵਿੱਚ ਸਟੋਰ ਕਰੋ.

ਅਗਲੇ ਕਦਮ ਵਿੱਚ, ਅਸੀਂ ਉਲਟਾ ਉਤਪਾਦ ਦੀ ਗਣਨਾ ਕਰ ਰਹੇ ਹਾਂ, ਇਸਦੇ ਨਾਲ, ਸਾਡਾ ਮਤਲਬ ਹੈ ਸੀਮਾ ਦੇ ਉਲਟ ਉਤਪਾਦ, ਜਿਵੇਂ ਕਿ ਜੇ ਅਸੀਂ ਆਈਥ ਇੰਡੈਕਸ ਤੱਕ ਉਲਟ ਉਤਪਾਦ ਦੀ ਗਣਨਾ ਕਰਦੇ ਹਾਂ, ਉਲਟਾ ਉਤਪਾਦ ਸਭ ਸੰਖਿਆਵਾਂ ਦਾ ਉਤਪਾਦ ਹੋਵੇਗਾ ਸੀਮਾ 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

ਜਟਿਲਤਾ ਵਿਸ਼ਲੇਸ਼ਣ

ਟਾਈਮ ਜਟਿਲਤਾ

ਓ (ਐਨ ਲੌਗ ਐਮ + ਕਿ Q), ਇੱਥੇ ਲਾਗ ਐਮ ਉਤਪਾਦ ਲਈ ਉਲਟਾ ਲੱਭਣ ਦੇ ਕਾਰਨ ਹੈ. ਅਤੇ ਫਿਰ ਸਵਾਲਾਂ ਦੇ ਜਵਾਬ ਦੇਣ ਲਈ O (Q).

ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ

ਓ (ਐਨ) ਜਿੱਥੇ ਕਿ “ਐਨ” ਐਰੇ ਵਿਚਲੇ ਤੱਤਾਂ ਦੀ ਗਿਣਤੀ ਹੈ. ਕਿਉਂਕਿ ਅਸੀਂ ਸਟੋਰ ਕੀਤਾ ਹੈ ਪ੍ਰੀਪ੍ਰੌਡਕਟ ਅਤੇ ਪ੍ਰੀਪ੍ਰੋਡਕਟਇੰਵਰਸ ਐਰੇ.