ஒரு வரிசையில் உள்ள வரம்புகளின் தயாரிப்புகள்


சிரமம் நிலை கடின
அடிக்கடி கேட்கப்படுகிறது அகோலைட் டி.இ ஷா ஃப்ரீசார்ஜ் கூகிள் 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] ஆகியவற்றின் தயாரிப்புகளைத் தருகிறோம். இது தேவையான பதிலாக இருக்கும்.

குறியீடு

ஒரு வரிசையில் வரம்புகளின் தயாரிப்புகளைக் கண்டறிய சி ++ குறியீடு

#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

ஒரு வரிசையில் வரம்புகளின் தயாரிப்புகளைக் கண்டறிய ஜாவா குறியீடு

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).

விண்வெளி சிக்கலானது

ஓ (என்) எங்கே “என்” என்பது வரிசையில் உள்ள உறுப்புகளின் எண்ணிக்கை. நாங்கள் சேமித்து வைத்ததால் முன் தயாரிப்பு மற்றும் preProductInverse வரிசைகள்.