প্রদত্ত ব্যাপ্তির উপাদান ব্যতীত অ্যারেগুলির সমস্ত সংখ্যার জিসিডির জন্য প্রশ্নগুলি eries  


কাঠিন্য মাত্রা কঠিন
প্রায়শই জিজ্ঞাসা করা হয় মর্দানী স্ত্রীলোক ক্যাপিটাল ওয়ান ডিই শ গুগল পেপ্যাল Quora তেরদাটা
বিন্যাস ডায়নামিক প্রোগ্রামিং GCD ম্যাথ প্রশ্ন সমস্যা

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

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

উদাহরণ  

arr[] = {1, 3, 6, 9}
Query: {(2, 3), (0, 1), (1, 2)}
1 3 1

ব্যাখ্যা

সূচক 2 থেকে 3 পর্যন্ত উপাদানগুলি বাদ দিয়ে উপাদানগুলির জিসিডি অর্থাত্, 1 এবং 3 এর জিসিডি হ'ল 1

এখন সূচক 0 থেকে 1 পর্যন্ত উপাদানগুলি বাদ দিয়ে উপাদানগুলির জিসিডি অর্থাৎ 6 এবং 9 এর জিসিডি 3 হয়

আবার সূচকে 1 থেকে 2 পর্যন্ত উপাদানগুলি বাদ দিয়ে উপাদানগুলির জিসিডি অর্থাৎ 1 এবং 9 এর জিসিডি হ'ল 1

প্রদত্ত ব্যাপ্তির উপাদান ব্যতীত অ্যারেগুলির সমস্ত সংখ্যার জিসিডির জন্য প্রশ্নগুলি eriesপিন

 

অ্যালগরিদম  

  1. প্রদত্ত ইনপুট অ্যারের মতো আকারের দুটি অ্যারে তৈরি করুন।
  2. অ্যারেটিকে 1 সূচী থেকে অ্যারের দৈর্ঘ্যে অতিক্রম করুন। তারপরে প্রিআররে পূর্ববর্তী সূচীতে সঞ্চিত বর্তমান উপাদান এবং উপাদানটির জিসিডি সন্ধান করুন এবং বর্তমান সূচীতে প্রাকআরেতে সংরক্ষণ করুন।
  3. ডান থেকে বামে অ্যারেটি অতিক্রম করুন এবং প্রত্যয়আর্রয় উপাদান এবং প্রদত্ত অ্যারে উপাদানটির জিসিডি সন্ধান করুন এবং জিসিডি প্রত্যয়আরেতে সঞ্চয় করুন।
  4. প্রতিটি প্রদত্ত ক্যোয়ারির জন্য, যদি বাম পরিসীমা 0 এর সমান হয়, তবে প্রত্যয়আরার [ডান + 1] এর মানটি ফিরিয়ে দিন।
  5. অন্যথায় যদি ডানের মান n - 1 এর সমান হয় তবে প্রিআরারের মান [বাম - 1] প্রদান করুন।
  6. অন্যথায় প্রিআর্রে [বাম -১] এর জিসিডি এবং প্রত্যয়আর্রে [ডান + ১] এর মান ফেরত দিন।
আরো দেখুন
এক্সপ্রেশন মূল্যায়ন

ব্যাখ্যা

উত্তর দেওয়ার জন্য পূর্ণসংখ্যার এবং কোয়েরির একটি অ্যারে দেওয়া হয়েছে। আমাদের এটি জানতে জিজ্ঞাসা করা হয়েছে বৃহত্তম সাধারণ বিভাজক ক্যোয়ারীর প্রদত্ত পরিসরে সমস্ত পূর্ণসংখ্যা ব্যতীত সংখ্যাগুলি of যদি আমাদের দৈর্ঘ্যের অ্যারেতে 0 থেকে 1 এর পরিসীমা দেওয়া হয় তবে এর অর্থ আমাদের অ্যারে [5] এবং অ্যারে [0] ব্যতীত সমস্ত পূর্ণসংখ্যার সবচেয়ে বড় সাধারণ বিভাজকটি খুঁজে বের করতে হবে। প্রদত্ত ক্যোয়ারীতে একটি ব্যাপ্তি হিসাবে বাম এবং ডান রয়েছে। আমাদের এই পরিসীমাটিতে আসা পূর্ণসংখ্যাগুলি ছেড়ে যেতে হবে।

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

প্রদত্ত ব্যাপ্তির প্রতিটি প্রদত্ত প্রশ্নের জন্য, প্রদত্ত বামদণ্ডটি 0 এর সমান কিনা তা পরীক্ষা করে দেখুন। সুতরাং প্রত্যয়আরারের মান [ডান + 1] প্রদান করুন। ডানটির মান অ্যারের দৈর্ঘ্যের সমান কিনা তা পরীক্ষা করে দেখুন। তারপরে প্রিআরারের মান [বাম -১] প্রদান করুন। অন্যথায় প্রিআররে বাম সূচিতে এলিমেন্টের সর্বশ্রেষ্ঠ সাধারণ বিভাজক এবং প্রত্যয়আররে ডান সূচীতে উপাদানটি ফিরে আসে return এটি আমাদের প্রয়োজনীয় উত্তর হবে।

আরো দেখুন
সর্বশেষে পৌঁছানোর জন্য সর্বনিম্ন জাম্পের সংখ্যা

কোড  

প্রদত্ত ব্যাপ্তি ব্যতীত অ্যারের GCD অনুসন্ধানের জন্য সি ++ কোড

#include<iostream>

using namespace std;
int __GCD(int a, int b)
{
    if (b == 0)
        return a;

    return __GCD(b, a % b);
}

void buildArrayOfGCD(int PreArray[], int arr[], int suffixArray[], int n)
{
    PreArray[0] = arr[0];
    for (int i=1 ; i<n; i++)
        PreArray[i] = __GCD(PreArray[i-1], arr[i]);

    suffixArray[n-1] = arr[n-1];

    for (int i=n-2; i>=0 ; i--)
        suffixArray[i] = __GCD(suffixArray[i+1], arr[i]);
}

int getGCDInRange(int l, int r, int PreArray[], int suffixArray[], int n)
{
    if (l==0)
        return suffixArray[r+1];

    if (r==n-1)
        return PreArray[l-1];
    return __GCD(PreArray[l-1], suffixArray[r+1]);
}

int main()
{
    int arr[] = {1, 3, 6, 9};
    int n = sizeof(arr)/sizeof(arr[0]);
    int PreArray[n], suffixArray[n];
    buildArrayOfGCD(PreArray, arr, suffixArray, n);

    int l = 2, r = 3;
    cout << getGCDInRange(l, r, PreArray, suffixArray, n)
         << endl;
    l = 0 ;
    r = 1;
    cout << getGCDInRange(l, r, PreArray, suffixArray, n)
         << endl;
    l = 1 ;
    r = 2;
    cout << getGCDInRange(l, r, PreArray, suffixArray, n)
         << endl;
    return 0;
}
1
3
1

প্রদত্ত ব্যাপ্তি ব্যতীত অ্যারের জিসিডি সন্ধানের জন্য জাভা কোড

import java.util.*;

class GCDNumbers
{
    static int GCD(int a, int b)
    {
        if (b == 0)
            return a;

        return GCD(b, a % b);
    }
    
    static void buildArrayOfGCD(int preArray[],int arr[], int suffixArray[], int n)
    {
        preArray[0] = arr[0];

        for (int i = 1; i < n; i++)
            preArray[i] = GCD(preArray[i - 1], arr[i]);

        suffixArray[n - 1] = arr[n - 1];

        for (int i = n - 2; i >= 0; i--)
            suffixArray[i] = GCD(suffixArray[i + 1], arr[i]);
    }

    static int getGCDInRange(int l, int r, int preArray[], int suffixArray[], int n)
    {

        if (l == 0)
            return suffixArray[r + 1];

        if (r == n - 1)
            return preArray[l - 1];

        return GCD(preArray[l - 1], suffixArray[r + 1]);
    }
    
    public static void main(String[] args)
    {
        int arr[] = { 1, 3, 6, 9};
        int n = arr.length;
        int preArray[] = new int[n];
        int suffixArray[] = new int[n];
        buildArrayOfGCD(preArray, arr, suffixArray, n);

        int l = 2, r = 3;
        System.out.println(getGCDInRange(l, r, preArray, suffixArray, n));

        l = 0;
        r = 1;
        System.out.println(getGCDInRange
                           (l, r, preArray, suffixArray, n));

        l = 1;
        r = 2;
        System.out.println(getGCDInRange
                           (l, r, preArray, suffixArray, n));
    }
}
1
3
1

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

সময় জটিলতা

O (N + Qlogn) কোথায় "প্রশ্ন" প্রশ্নের সংখ্যা এবং "N”হ'ল ইনপুট অ্যারেতে উপাদানগুলির সংখ্যা। চালু) প্রাকআররে এবং প্রত্যয়আরে তৈরির জন্য সময় প্রয়োজন। তারপরে O (Qlog n) প্রশ্নের উত্তরগুলির জন্য সময় প্রয়োজন কারণ প্রতিটি প্রশ্নের উত্তরের জন্য আমরা দুটি সংখ্যার জিসিডি খুঁজছি যা আমাদের লগ এনের জন্য ব্যয় করে যেখানে এন সংখ্যাটি এবং লগটি বেস 2 এর সাথে রয়েছে।

আরো দেখুন
পদক্ষেপ 1, 2 বা 3 ব্যবহার করে নবম সিঁড়িতে পৌঁছানোর উপায়গুলি গণনা করুন

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

প্রদত্ত ব্যাপ্তির উপাদান ব্যতীত অ্যারের সমস্ত সংখ্যার জিসিডির জন্য প্রশ্নগুলি সমাধান করার স্পেস জটিলতা চালু) কোথায় "এন" প্রিআর্রে এবং প্রত্যয়আরে সঞ্চয় করার জন্য অ্যারেতে থাকা উপাদানের সংখ্যা।