በተጠቀሰው ክልል ውስጥ ካሉ ንጥረ ነገሮች በስተቀር ለሁሉም የአንድ ድርድር ቁጥሮች የ GCD ጥያቄዎች


የችግር ደረጃ ጠንካራ
ውስጥ በተደጋጋሚ ተጠየቀ አማዞን አቢይ አንድ ዴ ሻው google የ PayPal Quora ተራዳታ
ሰልፍ ተለዋዋጭ ፕሮግራም GCD ሒሳብ የጥያቄ ችግር

የችግሩ መግለጫ

“በተወሰነ ክልል ውስጥ ካሉ ንጥረ ነገሮች በስተቀር የሁሉም ብዛት ቁጥሮች የ GCD ጥያቄዎች” ችግር እንደሚኖርዎት ይገልጻል ኢንቲጀር ደርድር እና q የጥያቄዎች ብዛት። እያንዳንዱ ጥያቄ ግራውን እና ቀኝ ቁጥርን ይይዛል። የችግሩ መግለጫ በተጠቀሰው መጠይቅ ውስጥ ካልሆነ በስተቀር የሁሉም ኢንቲጀሮች ትልቁ የጋራ አካፋይ ለማወቅ ይጠይቃል ፡፡

ለምሳሌ

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

ማስረጃ

ከመረጃ ጠቋሚ 2 እስከ 3 ያሉትን ንጥረ ነገሮችን የማይጨምር የ GCD አካላት ማለትም ፣ GCD ከ 1 እና 3 ነው 1

አሁን ከመረጃ ጠቋሚ 0 እስከ 1 ያሉትን ንጥረ ነገሮችን የማይጨምር የ GCD አካላት ማለትም ፣ GCD ከ 6 እና 9 ጋር 3 ነው

እንደገና ከመረጃ ጠቋሚ 1 እስከ 2 ያሉትን ንጥረ ነገሮችን የማይጨምር የ GCD አካላት ማለትም ፣ GCD ከ 1 እና 9 ጋር 1 ነው

በተጠቀሰው ክልል ውስጥ ካሉ ንጥረ ነገሮች በስተቀር ለሁሉም የአንድ ድርድር ቁጥሮች የ GCD ጥያቄዎች

 

አልጎሪዝም

  1. ከተሰጠው የግብዓት ድርድር ጋር ተመሳሳይ መጠን ያላቸው ሁለት ድርድሮችን ይፍጠሩ።
  2. ድርድርን ከ 1 መረጃ ጠቋሚ እስከ ድርድሩ ርዝመት ድረስ ያቋርጡ። ከዚያ በቅድመ-ማውጫ ውስጥ በቀዳሚው ማውጫ ላይ የተከማቸውን የአሁኑን ንጥረ-ነገር እና ኤለክት (GCD) ፈልጎ ያግኙ እና በቅድመ-አርራይ ውስጥ አሁን ባለው መረጃ ጠቋሚ ያከማቹ ፡፡
  3. ድርደራውን ከቀኝ ወደ ግራ በማለፍ የ “ቅጥያ” አሪራይ ንጥረ ነገር (GCD) እና የተሰጠውን የድርድር አካል ያግኙ እና GCD ን ወደ ቅጥያ አፋራይ ያከማቹ።
  4. ለእያንዳንዱ የተሰጠ ጥያቄ ፣ የግራው ክልል ከ 0 ጋር እኩል ከሆነ ፣ ከዚያ የቅጥያ ቅጥያ ዋጋን [ቀኝ + 1] ይመልሱ።
  5. አለበለዚያ የቀኝ እሴት ከ n - 1 ጋር እኩል ከሆነ ፣ ከዚያ የቅድመ ዝግጅት ዋጋን ይመልሱ [ግራ - 1]።
  6. አለበለዚያ የቅድመ-አደራሹን (የግራ -1) እና የቅጥያ አሬራይ [የቀኝ + 1] የ GCD ዋጋን ይመልሱ።

ማስረጃ

መልስ ለመስጠት ብዙ ቁጥር ያላቸው መጠይቆች እና ጥያቄዎች ተሰጥተዋል። እኛ እንድናውቅ ተጠይቀናል ትልቁ የጋራ መከፋፈል በተጠቀሰው የጥያቄ ክልል ውስጥ ካሉ ሁሉም ቁጥሮች በስተቀር ፡፡ በአንድ የርዝመት ርዝመት ከ 0 እስከ 1 ክልል ከተሰጠን 5. ይህ ማለት በድርድር ውስጥ ከአር [0] እና ከአር [1] በስተቀር የሁሉም ኢንቲጀሮች ትልቁን የጋራ መከፋፈያ መፈለግ አለብን ማለት ነው ፡፡ እንደ ክልል ግራ እና ቀኝ የያዘውን ጥያቄ የተሰጠ። በዚህ ክልል ውስጥ የሚመጡ ቁጥሮችን መተው አለብን ፡፡

ድርድርን እናቋርጣለን ግን ከዚያ በፊት የተሰጠውን ድርድር የመጀመሪያውን ንጥረ ነገር ወደ ቅድመ-አሪይ የመጀመሪያ አካል ይቅዱ ፡፡ ከዚያ በኋላ ድርድሩን ከግራ ወደ ቀኝ ያቋርጡ። በዚህ ጊዜ ቅድመ ዝግጅት እና ቅጥያ አሬይን እንገነባለን ፡፡ ለቅድመ ዝግጅት በዋናው የግቤት ድርድር እና በቀድሞ መረጃ ጠቋሚ ላይ ባለው ኤለመንት ውስጥ አሁን ባለው መረጃ ጠቋሚ ውስጥ ትልቁን የጋራ መለያ ክፍፍል ይፈልጉ። የእነዚህን ቁጥሮች GCD በቅድመ ዝግጅት ክፍል ውስጥ ያከማቹ። ከድርድሩ መሻገሪያ በኋላ ቅጥያ አሪራይ ይገንቡ። ለዚያ ፣ በአራይ ቅጥያ የመጨረሻው አካል ቦታ ላይ። የተሰጠው የድርድር አካል የመጨረሻውን ንጥረ ነገር ይቅዱ። ከዚያ በኋላ ለቅድመ ዝግጅት እኛ የምንከተለውን ተመሳሳይ አሰራር ይከተሉ ግን ከድርድሩ ከቀኝ ወደ ግራ።

ለተሰጠው ክልል ለእያንዳንዱ የተሰጠ መጠይቅ ፣ የተሰጠው የግራ ክልል ከ 0. ጋር እኩል መሆኑን ያረጋግጡ ፣ ስለሆነም የቅጥያ ቅጥያ [ቀኝ + 1] ዋጋን ይመልሱ። የቀኝ እሴት ከድርድሩ ርዝመት ጋር እኩል መሆኑን ያረጋግጡ። ከዚያ የቅድመ ዝግጅት ዋጋን [ግራ -1] ይመልሱ። ሌላኛው በፕራይራይ ውስጥ በግራ መረጃ ጠቋሚ ላይ ያለውን ንጥረ ነገር ትልቁን የጋራ መከፋፈያ እና በቀኝ ማውጫ በ suffixArray ውስጥ ይመልሳል ፡፡ ያ ተፈላጊ መልሳችን ይሆናል ፡፡

ኮድ

ከተጠቀሰው ክልል በስተቀር የ GCD ድርድርን ለማግኘት C ++ ኮድ

#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

ከተጠቀሰው ክልል በስተቀር የ GCD ድርድርን ለማግኘት የጃቫ ኮድ

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

ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ኦ (N + Qlogn) የት "ጥ" የጥያቄዎች ብዛት እና “N”በግብዓት ድርድር ውስጥ ያሉት ንጥረ ነገሮች ብዛት ነው። ኦ (ኤን) ለቅድመ ዝግጅት እና ቅጥያ አሬይ ግንባታ ጊዜ ያስፈልጋል። ከዚያ ኦ (Qlog n) ለጥያቄዎቹ መልስ ለመስጠት ጊዜ ያስፈልጋል ምክንያቱም ለእያንዳንዱ ጥያቄ መልስ ስናገኝ ሁለት ቁጥሮች ግ.ሲ.ድ. እያገኘን ነው ምዝግብ ማስታወሻ n የት ቁጥር እና ምዝግብ ከመሠረታዊ 2 ጋር ነው ፡፡

የቦታ ውስብስብነት

በተጠቀሰው ክልል ውስጥ ካሉ ንጥረ ነገሮች በስተቀር የሁሉም ብዛት ቁጥሮች ለ GCD ጥያቄዎችን ለመፍታት የቦታ ውስብስብነት ነው ኦ (ኤን) የት "N" የቅድመ ዝግጅት እና የ ‹ቅጥያ› አርራይትን ለማከማቸት በድርድሩ ውስጥ ያሉት ንጥረ ነገሮች ብዛት ነው።