數組中範圍的乘積  


難度級別
經常問 ol石 免費收費 谷歌 SAP實驗室 Snapdeal 時代互聯網
排列 模塊化算術 查詢問題

問題陳述  

問題“數組中的範圍的乘積”指出給您一個整數數組,該數組由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。 這樣,我們可以在固定時間內解決查詢。 我們不需要花費額外的精力來解決每個查詢。 現在,如果我們得到要解決的查詢,我們只需返回PreProduct [right]和PreInverseProduct [left-1]的乘積。 這將是必需的答案。

推薦碼  

C ++代碼在數組中查找範圍乘積

#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

Java代碼在數組中查找範圍乘積

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 log M + Q), 此處的日誌M是因為找到乘積的逆。 然後用O(Q)回答查詢。

也可以看看
單號

空間複雜度

上) 哪裡 “ N” 是數組中元素的數量。 因為我們存儲了 成品前產品逆 數組。