આપેલ શ્રેણીના તત્વો સિવાય એરેની તમામ સંખ્યાઓના જીસીડી માટે પ્રશ્નો


મુશ્કેલી સ્તર હાર્ડ
વારંવાર પૂછવામાં આવે છે એમેઝોન કેપિટલ વન ડીઇ શw Google પેપાલ Quora તેરાદાતા
અરે ડાયનેમિક પ્રોગ્રામિંગ જીસીડી મઠ ક્વેરી સમસ્યા

સમસ્યા નિવેદન

"આપેલ શ્રેણીના તત્વો સિવાય એરેની તમામ સંખ્યાના જીસીડી માટે પ્રશ્નો" સમસ્યા જણાવે છે કે તમને એક આપવામાં આવશે પૂર્ણાંક એરે અને 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 છે

આપેલ શ્રેણીના તત્વો સિવાય એરેની તમામ સંખ્યાઓના જીસીડી માટે પ્રશ્નો

 

અલ્ગોરિધમ

  1. આપેલા ઇનપુટ એરેની જેમ જ કદના બે એરે બનાવો.
  2. એરેને 1 અનુક્રમણિકાથી એરેની લંબાઈ સુધી ટ્રાવેલ કરો. પછી પ્રીરેમાં અગાઉના અનુક્રમણિકામાં સંગ્રહિત વર્તમાન તત્વ અને તત્વનું જીસીડી શોધી કા itો અને તેને પ્રીરેમાં વર્તમાન અનુક્રમણિકામાં સંગ્રહિત કરો.
  3. એરેને જમણેથી ડાબી તરફ વળો, અને પ્રત્યય એરે એલિમેન્ટના GCD અને આપેલા એરે એલિમેન્ટ શોધો અને જીસીડી પ્રત્યય એરેમાં સ્ટોર કરો.
  4. દરેક આપેલ ક્વેરી માટે, જો ડાબી શ્રેણી 0 ની બરાબર હોય, તો પછી પ્રત્યય એરે (મૂલ્ય + 1] ની કિંમત પરત કરો.
  5. બાકી જો જમણીનું મૂલ્ય n - 1 ની બરાબર હોય, તો પછી પ્રિઅરેય [ડાબે - 1] ની કિંમત પરત કરો.
  6. બાકી પ્રિઅર્રે [ડાબી -1] ની જીસીડીનું મૂલ્ય અને પ્રત્યય એરે (જમણે + 1] ની વળતર.

સમજૂતી

પૂર્ણાંકો અને જવાબો આપવા માટેના પ્રશ્નોની એરે આપી. અમને શોધવા માટે કહેવામાં આવે છે મહાન સામાન્ય વિભાજક ક્વેરીની આપેલ શ્રેણીમાં બધા પૂર્ણાંકો સિવાય સંખ્યાઓની સંખ્યા. જો આપણને લંબાઈના એરેમાં 0 થી 1 ની શ્રેણી આપવામાં આવે છે. આનો અર્થ એ કે આપણે એરે [5] અને એરે [0] સિવાય એરે સિવાય બધા પૂર્ણાંકોનો સૌથી મોટો સામાન્ય વિભાજક શોધવા પડશે. આપેલ ક્વેરી જેમાં રેન્જ તરીકે ડાબે અને જમણે સમાવિષ્ટ છે. આપણે આ શ્રેણીમાં આવતા પૂર્ણાંકો છોડવાના છે.

આપણે એરેને પસાર કરીશું, પરંતુ તે પહેલાં આપેલ એરેના પ્રથમ તત્વને પ્રીરેનના પ્રથમ તત્વમાં નકલ કરો. તે પછી એરે ડાબીથી જમણી તરફ વટાવી દો. આ સમય દરમિયાન આપણે પ્રીઅરે અને પ્રત્યયઅરે બનાવીશું. પ્રીઅરે માટે મૂળ ઇનપુટ એરેમાં વર્તમાન અનુક્રમણિકામાં તત્વનો સૌથી સામાન્ય સામાન્ય વિભાજક અને પ્રિઅરેમાં અગાઉના અનુક્રમણિકામાં તત્વ શોધી કા .ો. આ નંબરોનું આ જીસીડી પ્રીરે એલિમેન્ટમાં સ્ટોર કરો. એરેના ટ્રversવર્સલ પછી, પ્રત્યય એરે બનાવવો. તે માટે, પ્રત્યય એરેના અંતિમ તત્વની જગ્યાએ. આપેલ એરે એલિમેન્ટના એરેના છેલ્લા એલિમેન્ટની ક Copyપિ કરો. તે પછી તે જ પ્રક્રિયાને અનુસરો જેમ આપણે પ્રિઅરે માટે અનુસરીએ છીએ પરંતુ એરેની જમણીથી ડાબી બાજુ.

આપેલ શ્રેણીની દરેક આપેલ ક્વેરી માટે, આપેલ ડાબી શ્રેણી 0 ની બરાબર છે કે નહીં તેની તપાસ કરો. જમણીનું મૂલ્ય એરેની લંબાઈ જેટલું છે કે નહીં તે તપાસો. પછી પ્રીઅર્રે [ડાબી -1] ની કિંમત પરત કરો. બાકી પ્રિઅર્રેમાં ડાબું અનુક્રમણિકામાં તત્વનો સૌથી સામાન્ય સામાન્ય વિભાજક અને પ્રત્યય એરેમાં જમણા અનુક્રમણિકામાં તત્વનો પાછા ફરો. તે અમારો જરૂરી જવાબ હશે.

કોડ

આપેલ શ્રેણી સિવાય એરેના જીસીડી શોધવા માટે સી ++ કોડ

#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”એ ઇનપુટ એરેમાં તત્વોની સંખ્યા છે. ઓ (એન) પ્રીઅરે અને પ્રત્યય એરેના નિર્માણ માટે સમય આવશ્યક છે. પછી ઓ (ક્લોગ એન) પ્રશ્નોનો જવાબ આપવા માટે સમય જરૂરી છે કારણ કે દરેક ક્વેરીના જવાબ માટે આપણે બે નંબરોની જીસીડી શોધી રહ્યા છીએ જે આપણને લ logગ કરે છે જ્યાં એન નંબર છે અને લોગ બેઝ 2 સાથે છે.

અવકાશ જટિલતા

આપેલ શ્રેણીના તત્વો સિવાય એરેની તમામ સંખ્યાના જીસીડી માટે ક્વેરીઝ હલ કરવાની જગ્યાની જટિલતા છે ઓ (એન) જ્યાં “એન” પ્રીરે અને પ્રત્યય એરે સંગ્રહવા માટે એરેમાં તત્વોની સંખ્યા છે.