배열에있는 범위의 곱


난이도 하드
자주 묻는 질문 Accolite DE Shaw FreeCharge 구글 SAP 연구소 스냅 딜 타임즈 인터넷
배열 모듈 식 산술 쿼리 문제

문제 정책

"배열에있는 범위의 곱"문제는 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는 동일하게 유지됩니다.

배열에있는 범위의 곱

접근

숫자의 범위를 시작 번호와 끝 번호로 지정 번호. 이 범위는 모든 중간 숫자로 채워져 있으므로 고려하십시오. 우리의 임무는이 범위 내에서 숫자의 곱을 찾는 것입니다. 제품과 역 곱을 계산 한 다음 나중에 쿼리를 해결합니다.이 두 단계의 사전 제품과 역 곱을 계산하여 한 번에 여러 쿼리를 해결합니다. 쿼리를 해결하기 위해 전체 알고리즘을 거쳐야합니다.

먼저 배열의 사전 곱을 계산합니다. 즉, 배열을 탐색해야하며, 먼저 주어진 배열의 첫 번째 요소를 사전 곱 배열의 첫 번째 요소에 복사해야합니다. 주어진 배열의 첫 번째 위치에서 배열을 순회하고 주어진 배열과 곱 배열의 이전 요소의 곱을 저장합니다. 모듈로를 유지하기 위해 우리가 얻은 제품의 모듈로를 저장합니다 제품 배열에 저장합니다.

다음 단계에서 우리는 역 곱을 계산할 것입니다. 이는 범위의 역 곱을 의미하므로 i 번째 인덱스까지 역 곱을 계산하면 역 곱이 모든 숫자의 곱이됩니다. 범위 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), 여기서 log M은 제품의 역수를 찾기 때문입니다. 그리고 질문에 답하기위한 O (Q).

공간 복잡성

의 위에) 어디에 "엔" 배열의 요소 수입니다. 우리가 저장했기 때문에 preProductpreProductInverse 배열.