Bir sıra aralıkların məhsulları

Çətinlik səviyyəsi Ağır
Tez-tez soruşulur Akkolit DE Şou Pulsuz yükləmə google SAP Laboratoriyaları Snapdeal Times İnternet
Geyim Modul hesabı Sorğu problemiBaxılıb 20

Problem bəyanat

"Bir sıra içərisindəki məhsullar" problemi sizə 1-dən n-ə və q sorğu sayından ibarət ədədlərdən ibarət bir tam sıra verildiyini bildirir. Hər sorğu aralığı ehtiva edir. Problem ifadəsi, m-nin hər hansı bir sadə ədədi olduğu M modulu altında verilmiş aralığında məhsulu tapmağı xahiş edir.

misal

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

M = 131

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

Izahat 

1-dən 6-a qədər, modul tətbiq edildikdə, sıra məhsulu 720'dir və 65 qalır və 24 eyni qalır.

Bir sıra aralıkların məhsullarıPin

Yanaşma

Başlanğıc və son olaraq bir sıra aralığı verilmişdir nömrə. Bu aralığın içindəki bütün rəqəmlərlə doldurulduğunu nəzərə alaraq. Bizim vəzifəmiz bu aralıqdakı rəqəmlərin məhsulunu tapmaqdır. Məhsulu və tərs məhsulu hesablayacağıq, daha sonra sorğunu həll edəcəyik, bununla da əvvəlcədən məhsulu və tərs məhsulu hesablamanın iki mərhələsi, eyni anda birdən çox sorğu həll edəcəyik ' bir sorğunu həll etmək üçün bütün alqoritmdən keçmək lazımdır.

Əvvəlcə serialın əvvəl məhsulunu hesablayın, yəni serialı keçməliyik və ilk növbədə verilmiş massivin ilk elementini məhsuldan əvvəlki serialın ilk elementinə kopyalamalıyıq. Verilən massivin ilk mövqeyindən serialı keçəcəyik və verilmiş massivin əvvəlki elementinin məhsulunu və məhsul massivini saxlayacağıq, modulunu qorumaq üçün əldə etdiyimiz məhsulun modulunu saxlayacağıq və məhsul seriyasında saxla.

Növbəti addımda tərs məhsulu hesablayacağıq, bununla aralığın tərs məhsulunu nəzərdə tuturuq ki, tərs məhsulu ith indeksinə qədər hesablasaq, tərs məhsul bütün rəqəmlərin məhsulu olacaq. 0-dan i-yə qədər. Bununla sorğunu daimi vaxtda həll edə bilərik. Hər bir sorğunun həlli üçün əlavə səy göstərməyimizə ehtiyac yoxdur. İndi sorğunu həll etsək, PreProduct [sağ] və PreInverseProduct [sol-1] məhsulunu qaytarırıq. Bu tələb olunan cavab olacaq.

Kodu

Bir sıra içərisində məhsul tapmaq üçün C ++ kodu

#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

Bir sıra içərisindəki məhsulları tapmaq üçün Java kodu

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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (N log M + Q), burada log M məhsulun tərsini tapmasıdır. Və sonra sualları cavablandırmaq üçün O (Q).

Kosmik Mürəkkəblik

O (N) hara "N" massivdəki elementlərin sayıdır. Çünki saxladıq əvvəlcədən məhsulpreProductTers massivlər.

Translate »