একটি অ্যারেতে প্রদত্ত সূচকের রেসিডির জিসিডি


কাঠিন্য মাত্রা কঠিন
প্রায়শই জিজ্ঞাসা করা হয় ডিই শ পেপ্যাল Snapchat Snapdeal টাইমস ইন্টারনেট জুম
বিন্যাস প্রশ্ন সমস্যা সেগমেন্ট-ট্রি গাছ

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

সমস্যাটি 'প্রদত্ত সূচকের জিসিডিগুলিকে একটি অ্যারেতে রেঞ্জ করা হয় "তাতে উল্লেখ করা হয় যে আপনাকে একটি দেওয়া হয়েছে পূর্ণসংখ্যা বিন্যাস এবং কিছু পরিসীমা অনুসন্ধান। সমস্যার বিবৃতিটি পরিসরের মধ্যে গঠিত সাব-অ্যারেটির সর্বশ্রেষ্ঠ সাধারণ বিভাজকটি অনুসন্ধান করতে বলে।

উদাহরণ

arr[] = {10, 5, 18, 9, 24}
Query: {(0, 1), (2, 4), (0, 3)}
5 3 1

ব্যাখ্যা

প্রথম ক্যোয়ারীর সর্বশ্রেষ্ঠ সাধারণ বিভাজক 0 এবং 1 এর মধ্যে থাকে, সুতরাং 10 এবং 5 এর জিসিডি 5 হয়।

দ্বিতীয় ক্যোয়ারির জিসিডি 2 এবং 4 এর মধ্যে রয়েছে, তাই 18, 9, 24 এর জিসিডি 3 হয়।

প্রথম ক্যোয়ারীর সর্বশ্রেষ্ঠ সাধারণ বিভাজক 0 এবং 3 এর মধ্যে থাকে, সুতরাং জিসিডি 1 হয়।

একটি অ্যারেতে প্রদত্ত সূচকের রেসিডির জিসিডি

 

অ্যালগরিদম

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

ব্যাখ্যা

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

আমরা অ্যারের 0 তম অবস্থান থেকে অ্যারের শেষ অবস্থানে সেগমেন্ট গাছটি তৈরি করা শুরু করব এবং গুরুত্বপূর্ণ অংশটি অ্যারেটিকে দুটি অংশে বিভক্ত করছে। অ্যারের দৈর্ঘ্য এক না হওয়া পর্যন্ত আমরা এটির বিভাজন অবিরত করব, তারপরে পরবর্তী ধাপে পুনরাবৃত্তভাবে অ্যারের উভয় অংশে ফাংশনটি কল করব call এখানে আমরা একটি গাছের নোডে সর্বশ্রেষ্ঠ সাধারণ বিভাজকটি সংরক্ষণ করব। সমস্ত অভ্যন্তরীণ নোড পাতার নোড বাদে নਾਲ হবে না। এতটা গঠিত গাছটি বাইনারি গাছ হবে। কারণ প্রতিটি নোড স্তরে অ্যারের দুটি অংশ রয়েছে। তবে একটি বাইনারি গাছের সাথে তুলনা করুন, যেখানে নোডগুলি একটি সংখ্যার পরিবর্তে একটি ব্যাপ্তি উপস্থাপন করে।

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

কোড

অ্যারেতে প্রদত্ত সূচী রেঞ্জের জিসিডি সন্ধান করতে সি ++ কোড

#include<iostream>
#include<math.h>

using namespace std;

int *segTree;

int gcd(int a, int b)
{
    if (a < b)
    {
        int temp = b;
        b = a;
        a = temp;
    }

    if (b==0)
        return a;
    return gcd(b,a%b);
}

int getGCDOfNumber(int startNode, int endNode, int startQuery, int endQuery, int si)
{
    if (startNode>endQuery || endNode < startQuery)
        return 0;
    if (startQuery<=startNode && endQuery>=endNode)
        return segTree[si];

    int mid = startNode+(endNode-startNode)/2;

    return gcd(getGCDOfNumber(startNode, mid, startQuery, endQuery, si*2+1),
               getGCDOfNumber(mid+1, endNode, startQuery, endQuery, si*2+2));
}

int findRangeGcd(int startNode, int endNode, int arr[],int n)
{
    if (startNode<0 || endNode > n-1 || startNode>endNode)
    {
        cout << "Invalid Arguments" << "\n";
        return -1;
    }
    return getGCDOfNumber(0, n-1, startNode, endNode, 0);
}

int buildSegementTree(int arr[], int startNode, int endNode, int si)
{
    if (startNode==endNode)
    {
        segTree[si] = arr[startNode];
        return segTree[si];
    }
    int mid = startNode+(endNode-startNode)/2;

    segTree[si] = gcd(buildSegementTree(arr, startNode, mid, si*2+1),
                      buildSegementTree(arr, mid+1, endNode, si*2+2));
    return segTree[si];
}

int *constructendNodegmentTree(int arr[], int n)
{
    int height = (int)(ceil(log2(n)));
    int size = 2*(int)pow(2, height)-1;
    segTree = new int[size];
    buildSegementTree(arr, 0, n-1, 0);
    return segTree;
}

int main()
{
    int a[] = {10, 5, 18, 9, 24};
    int n = sizeof(a)/sizeof(a[0]);

    constructendNodegmentTree(a, n);

    int l = 0, r = 1;
    cout << "Greatest Common Divisor is: ";
    cout << findRangeGcd(l, r, a, n) << "\n";

    l = 2;
    r = 4;
    cout << "Greatest Common Divisor is: ";
    cout << findRangeGcd(l, r, a, n) << "\n";

    l = 0;
    r = 3;
    cout << "Greatest Common Divisor is: ";
    cout << findRangeGcd(l, r, a, n) << "\n";

    return 0;
}
Greatest Common Divisor is: 5
Greatest Common Divisor is: 3
Greatest Common Divisor is: 1

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

import java.io.*;

public class GCDOfNumber
{
    private static int[] segTree;

    public static int[] buildSegmentTree(int[] arr)
    {
        int height = (int)Math.ceil(Math.log(arr.length)/Math.log(2));
        int size = 2*(int)Math.pow(2, height)-1;
        segTree = new int[size];
        SegementTree(arr, 0, arr.length-1, 0);

        return segTree;
    }

    public static int SegementTree(int[] arr, int startNode,
                                   int endNode, int si)
    {
        if (startNode==endNode)
        {
            segTree[si] = arr[startNode];

            return segTree[si];
        }
        int mid = startNode+(endNode-startNode)/2;

        segTree[si] = gcd(SegementTree(arr, startNode, mid, si*2+1),
                          SegementTree(arr, mid+1, endNode, si*2+2));
        return segTree[si];
    }

    private static int gcd(int a, int b)
    {
        if (a < b)
        {
            int temp = b;
            b = a;
            a = temp;
        }

        if (b==0)
            return a;
        return gcd(b,a%b);
    }

    public static int findRangeGcd(int startNode, int endNode, int[] arr)
    {
        int n = arr.length;

        if (startNode<0 || endNode > n-1 || startNode>endNode)
            throw new IllegalArgumentException("Invalid arguments");

        return findGcd(0, n-1, startNode, endNode, 0);
    }

    public static int findGcd(int startNode, int endNode, int startQuery, int endQuery, int si)
    {
        if (startNode>endQuery || endNode < startQuery)
            return 0;

        if (startQuery<=startNode && endQuery>=endNode)
            return segTree[si];

        int mid = startNode+(endNode-startNode)/2;

        return gcd(findGcd(startNode, mid, startQuery, endQuery, si*2+1),
                   findGcd(mid+1, endNode, startQuery, endQuery, si*2+2));
    }

    public static void main(String[] args)throws IOException
    {
        int[] a = {10, 5, 18, 9, 24};

        buildSegmentTree(a);

        int l = 0, r = 1;
        System.out.println("Greatest Common Divisor is: "+findRangeGcd(l, r, a));

        l = 2;
        r = 4;
        System.out.println("Greatest Common Divisor is: "+findRangeGcd(l, r, a));

        l = 0;
        r = 3;
        System.out.println("Greatest Common Divisor is: "+findRangeGcd(l, r, a));
    }
}
Greatest Common Divisor is: 5
Greatest Common Divisor is: 3
Greatest Common Divisor is: 1

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

সময় জটিলতা

ও (এন লগ এন + লগ এন * লগ (মিনিট (ক, খ))) কোথায় "এন" নোড এবং "একটি" এবং "খ" যে নোডগুলি হ'ল মার্জড অপারেশনের সময় যার জিসিডি গণনা করা হয়। ও (এন লগন) সময় নির্মাণের জন্য ব্যয় করা হয় এবং ও (লগ এন) প্রতিটি প্রশ্নের উত্তর এবং তারপর ও (লগ (মিনিট (ক, খ))) জিসিডি সন্ধানের সময়

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

উপর) কোথায় "এন" নোড হয় একটি সেগমেন্ট গাছ তৈরিতে জায়গা ব্যয় করা হয়।