किसी श्रेणी में तत्वों को छोड़कर किसी सरणी की सभी संख्याओं के GCD के लिए प्रश्न


कठिनाई स्तर कठिन
में अक्सर पूछा वीरांगना एक राजधानी डीई शॉ गूगल पेपैल Quora Teradata
ऐरे गतिशील प्रोग्रामिंग GCD मठ क्वेरी की समस्या

समस्या का विवरण

"किसी श्रेणी में तत्वों को छोड़कर किसी सरणी के सभी संख्याओं के GCD के लिए प्रश्न" समस्या बताती है कि आपको a दिया जाएगा पूर्णांक सरणी और एक q प्रश्नों की संख्या। प्रत्येक क्वेरी में बाईं और दाईं ओर संख्या होती है। समस्या कथन प्रश्न की दी गई सीमा के अलावा सभी पूर्णांकों के सबसे बड़े सामान्य विभाजक का पता लगाने के लिए कहता है।

उदाहरण

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

व्याख्या

इंडेक्स 2 से 3 के तत्वों को छोड़कर तत्वों का GCD यानी 1 और 3 का GCD 1 है

अब सूचकांक 0 से 1 तक के तत्वों को छोड़कर तत्वों का GCD अर्थात 6 और 9 का GCD 3 है

फिर इंडेक्स 1 से 2 के तत्वों को छोड़कर तत्वों का GCD यानी 1 और 9 का GCD 1 है

किसी श्रेणी में तत्वों को छोड़कर किसी सरणी की सभी संख्याओं के GCD के लिए प्रश्न

 

कलन विधि

  1. दिए गए इनपुट ऐरे के समान आकार के दो ऐरे बनाएं।
  2. सरणी की लंबाई के लिए 1 इंडेक्स से सरणी को पार करें। फिर पूर्ववर्ती में पिछले सूचकांक में संग्रहीत वर्तमान तत्व और तत्व के जीसीडी का पता लगाएं और इसे पूर्व में वर्तमान सूचकांक में संग्रहीत करें।
  3. सरणी को दाईं ओर से बाईं ओर ले जाएं, और प्रत्यय एरे तत्व का जीसीडी और दिए गए सरणी तत्व का पता लगाएं और जीसीडी को प्रत्ययअरे में संग्रहीत करें।
  4. प्रत्येक दिए गए प्रश्न के लिए, यदि बाईं सीमा 0 के बराबर है, तो प्रत्यय का मान लौटाएं [सही + 1]।
  5. और यदि दाईं ओर का मान n - 1 के बराबर है, तो पूर्ववर्ती [बाएँ - 1] का मान लौटाएं।
  6. एले प्रीरेयर [लेफ्ट -1] और प्रत्यय [राइट + 1] के जीसीडी का मान लौटाते हैं।

व्याख्या

जवाब देने के लिए पूर्णांक और प्रश्नों की एक सरणी दी। हमें इसका पता लगाने के लिए कहा जाता है महत्तम सामान्य भाजक क्वेरी की दी गई श्रेणी में सभी पूर्णांकों को छोड़कर संख्याओं का। अगर हमें लम्बाई के सरणी में 0 से 1 तक की सीमा दी जाती है। इसका मतलब है कि हमें एक सरणी में गिरफ्तार [5] और गिरफ्तारी [0] को छोड़कर सभी पूर्णांकों का सबसे बड़ा सामान्य भाजक ज्ञात करना होगा। दी गई क्वेरी जिसमें एक सीमा के रूप में बाएँ और दाएँ शामिल हैं। हमें इस सीमा में आने वाले पूर्णांकों को छोड़ना होगा।

हम सरणी को पीछे ले जा रहे हैं, लेकिन इससे पहले दिए गए सरणी के पहले तत्व को प्रीअर्रे के पहले तत्व में कॉपी करें। उसके बाद सरणी को बाएं से दाएं की ओर ले जाएं। इस समय के दौरान हम पूर्वग्रह और प्रत्यय का निर्माण करेंगे। PreArray के लिए मूल इनपुट सरणी में वर्तमान सूचकांक में तत्व का सबसे बड़ा सामान्य भाजक पता करें और पिछले सरणी में तत्व का पता लगाएं। PreArray तत्व में इन संख्याओं के GCD को संग्रहीत करें। सरणी के ट्रैवर्सल के बाद, प्रत्यय बनाएँ। उसके लिए, प्रत्यय के अंतिम तत्व की जगह पर। दिए गए सरणी तत्व के अंतिम तत्व की प्रतिलिपि बनाएँ। उसके बाद उसी प्रक्रिया का पालन करें जैसा कि हम प्रीरे के लिए करते हैं लेकिन एरो के दाईं से बाईं ओर।

दी गई सीमा के प्रत्येक दिए गए क्वेरी के लिए, जाँच करें कि दी गई बाईं सीमा 0. के बराबर है। जांचें कि क्या सही का मान सरणी की लंबाई के बराबर है। फिर प्रीएरे के मूल्य को छोड़ दें [बाएं -1]। एलीस प्रीरेयर में लेफ्ट इंडेक्स में एलिमेंट के सबसे बड़े कॉमन डिविजर और राइट इंडेक्स में एरीकेयर में एलिमेंट को रिटर्न करता है। वह हमारा आवश्यक उत्तर होगा।

कोड

किसी दिए गए श्रेणी को छोड़कर सरणी का 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

जटिलता विश्लेषण

समय जटिलता

O (N + Qlogn) जहां 'क्यू' प्रश्नों की संख्या है और "N"इनपुट ऐरे में तत्वों की संख्या है। पर) PreArray और प्रत्यय के निर्माण के लिए समय आवश्यक है। फिर ओ (क्लॉग एन) प्रश्नों का उत्तर देने के लिए समय की आवश्यकता होती है क्योंकि प्रत्येक प्रश्न के उत्तर के लिए हम दो संख्याओं के gcd पा रहे हैं, जिसकी लागत हमें n n लगती है जहाँ n संख्या है और लॉग आधार 2 के साथ है।

अंतरिक्ष जटिलता

किसी श्रेणी में तत्वों को छोड़कर किसी सरणी की सभी संख्याओं के GCD के लिए क्वेरी को हल करने के लिए अंतरिक्ष जटिलता है पर) जहां "एन" सरणी में तत्वों की संख्या प्रीएयर और प्रत्यय स्टोर करने के लिए है।