数组中范围的乘积


难度级别
经常问 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” 是数组中元素的数量。 因为我们存储了 成品前产品逆 数组。