Маҳсулоти диапазонҳо дар массив  


Сатҳи душворӣ мушкил
Аксар вақт пурсида мешавад Акколити DE Шо FreeCharge Google Лабораторияҳои SAP Snapdeal Интернет Times
тартиботи ҳарбӣ Арифметикаи модулӣ Масъалаи пурсиш

Изҳороти мушкилот  

Масъалаи "Маҳсулоти диапазонҳо дар массив" мегӯяд, ки ба шумо массиви бутуни иборат аз рақамҳо аз 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 бетағйир боқӣ мемонад.

Маҳсулоти диапазонҳо дар массивпайвандак

усул  

Бо назардошти диапазони рақам ҳамчун рақами ибтидоӣ ва хотима шумора. Бо назардошти ин диапазон, вақте ки он бо ҳама рақамҳои байниҳам пур карда шудааст. Вазифаи мо аз он иборат аст, ки ҳосили рақамҳои рақамҳоро дар ин диапазон муайян кунем. Мо маҳсулот ва маҳсулоти баръаксро ҳисоб карда истодаем, баъд, баъдтар, мо дархостро ҳал хоҳем кард, бо ин, ду марҳилаи ҳисобкунии маҳсулоти пешакӣ ва баръакс, мо дар як вақт саволҳои сершуморро ҳал хоҳем кард, мо донем ' t барои ҳалли дархост аз тамоми алгоритм гузаштан лозим аст.

Аввалан, маҳсули пешакии массивро ҳисоб кунед, яъне мо бояд массивро тай намоем ва пеш аз ҳама, мо бояд элементи якуми массиви додашударо ба унсури якуми массиви пеш аз маҳсулот нусхабардорӣ намоем. Мо массивро аз мавқеи аввали массиви додашуда убур намуда, маҳсули унсури қаблии массиви додашуда ва массиви маҳсулотро нигоҳ медорем, то модулро нигоҳ дорем, модули маҳсули ба даст овардаро нигоҳ медорем ва онро ба массиви маҳсулот нигоҳ доред.

ҳамчунин нигаред
Дарозии пайдоиши Фибоначчи дарозтарин

Дар қадами оянда, мо ҳосили баръаксро ҳисоб мекунем, бо ин, мо ҳосили баръакси диапазонро дар назар дорем, ки агар ҳосили баръаксро то индекси ith ҳисоб кунем, ҳосили баръакс ҳосили ҳамаи ададҳо хоҳад буд аз диапазони 0 то i. Бо ин, мо метавонем дархостро дар вақти доимӣ ҳал кунем. Барои ҳалли ҳар як савол ба мо кӯшиши иловагӣ лозим нест. Ҳоло, агар мо дархости ҳалли худро пайдо кунем, мо танҳо маҳсулоти PreProduct [рост] ва PreInverseProduct [чап-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" шумораи унсурҳои массив аст. Зеро мо захира кардем маҳсулоти пешакӣ ва preProductInverse массиви.