একটি অ্যারেতে ব্যাপ্তিগুলির পণ্য


কাঠিন্য মাত্রা কঠিন
প্রায়শই জিজ্ঞাসা করা হয় সমষ্টি ডিই শ ফ্রিচার্জ গুগল এসএপি ল্যাব Snapdeal টাইমস ইন্টারনেট
বিন্যাস মডুলার গাণিতিক প্রশ্ন সমস্যা

সমস্যা বিবৃতি

"একটি অ্যারেতে রেঞ্জের পণ্যগুলি" সমস্যাটি বলে যে আপনাকে সংখ্যার 1 থেকে এন এবং কিউয়ের সংখ্যার সমন্বয়ে একটি পূর্ণসংখ্যা অ্যারে দেওয়া হয়। প্রতিটি ক্যোয়ারিতে ব্যাপ্তি থাকে। সমস্যা বিবরণীটি মডুলো এম এর অধীনে প্রদত্ত রেঞ্জের মধ্যে পণ্যটি খুঁজে বের করতে বলে যেখানে এম যে কোনও মৌলিক সংখ্যা।

উদাহরণ

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

M = 131

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

ব্যাখ্যা 

1 থেকে 6 অবধি, মডুলোর প্রয়োগ করা হয় তখন পরিসরের গুণমান 720 হয় যখন এটি 65 টি ছেড়ে 24 টি একই থাকে।

একটি অ্যারেতে ব্যাপ্তিগুলির পণ্য

অভিগমন

একটি শুরুর সংখ্যা এবং শেষ হিসাবে একটি সংখ্যার ব্যাপ্তি দেওয়া সংখ্যা। এই পরিসীমাটিকে বিবেচনা করা হচ্ছে কারণ এটি এর মধ্যে থাকা সমস্ত সংখ্যার সাথে পূর্ণ। আমাদের কাজটি এই ব্যাপ্তির মধ্যে নম্বর সংখ্যার পণ্যটি সন্ধান করা। আমরা পণ্যটি এবং বিপরীতমুখী পণ্য গণনা করব, তারপরে, আমরা প্রাক-পণ্য এবং বিপরীত পণ্য গণনা করার দুটি ধাপের সাহায্যে, ক্যোয়ারির সমাধান করব, আমরা একসাথে একাধিক প্রশ্ন সমাধান করব, আমরা ডন ' কোন প্রশ্নের সমাধান করার জন্য পুরো অ্যালগরিদমটি দিয়ে যাওয়া দরকার।

প্রথমে অ্যারের প্রাক-পণ্য গণনা করুন, অর্থাৎ আমাদের অ্যারেটি অতিক্রম করতে হবে এবং সবার আগে আমাদের প্রদত্ত অ্যারের প্রথম উপাদানটি প্রাক-পণ্য অ্যারের প্রথম উপাদানটিতে অনুলিপি করতে হবে। আমরা প্রদত্ত অ্যারের প্রথম অবস্থান থেকে অ্যারেটি অতিক্রম করব এবং প্রদত্ত অ্যারের পূর্ববর্তী উপাদান এবং পণ্য অ্যারের পণ্য সংরক্ষণ করব, মডিউলগুলি বজায় রাখার জন্য, আমরা যে পণ্যটি পেয়েছি তার মডিউলগুলি সংরক্ষণ করব এবং এটি পণ্য অ্যারেতে সঞ্চয় করুন।

পরবর্তী পদক্ষেপে, আমরা বিপরীত পণ্য গণনা করব, এটির সাথে আমরা ব্যাপ্তিটির বিপরীত পণ্যটি বোঝাচ্ছি, যেমন আমরা আইথ সূচক পর্যন্ত বিপরীত পণ্য গণনা করি, বিপরীত পণ্যটি সমস্ত সংখ্যার গুণফল হবে 0 থেকে i ব্যাপ্তি পর্যন্ত। এটির সাহায্যে আমরা স্থির সময়ে প্রশ্নের সমাধান করতে পারি। প্রতিটি প্রশ্নের সমাধান করার জন্য আমাদের অতিরিক্ত প্রচেষ্টা করার দরকার নেই need এখন যদি আমরা সমাধানের জন্য ক্যোয়ারীটি পাই তবে আমরা কেবলমাত্র প্রিপ্রডাক্ট [ডান] এবং প্রিআইনভারসপ্রডাক্ট [বাম -১] এর পণ্যটি ফিরিয়ে দেব। এটি প্রয়োজনীয় উত্তর হবে।

কোড

একটি অ্যারেতে রেঞ্জের পণ্যগুলি খুঁজতে সি ++ কোড

#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

জটিলতা বিশ্লেষণ

সময় জটিলতা

ও (এন লগ এম + কিউ), এখানে লগ এম পণ্যের জন্য বিপরীতমুখী সন্ধানের কারণ। এবং তারপরে প্রশ্নের উত্তর দেওয়ার জন্য ও (প্রশ্ন)

স্পেস জটিলতা ity

চালু) কোথায় "এন" অ্যারেতে উপাদানগুলির সংখ্যা। কারণ আমরা সংরক্ষণ করেছি প্রিপ্রডাক্ট এবং প্রাকপ্রডাক্ট ইনভারস অ্যারে।