ఇచ్చిన పరిధిలోని అంశాలు మినహా శ్రేణి యొక్క అన్ని సంఖ్యల యొక్క GCD కోసం ప్రశ్నలు


కఠినత స్థాయి హార్డ్
తరచుగా అడుగుతుంది అమెజాన్ కాపిటల్ వన్ డిఇ షా గూగుల్ పేపాల్ కోరా Teradata
అర్రే డైనమిక్ ప్రోగ్రామింగ్ గ.సా.భా. మఠం ప్రశ్న సమస్య

సమస్యల నివేదిక

“ఇచ్చిన పరిధిలోని మూలకాలు మినహా శ్రేణి యొక్క అన్ని సంఖ్యల జిసిడి కోసం ప్రశ్నలు” సమస్య మీకు ఇవ్వబడుతుంది పూర్ణ సంఖ్య అమరిక మరియు ఒక 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

ఇచ్చిన పరిధిలోని అంశాలు మినహా శ్రేణి యొక్క అన్ని సంఖ్యల యొక్క GCD కోసం ప్రశ్నలు

 

అల్గారిథం

  1. ఇచ్చిన ఇన్పుట్ శ్రేణికి సమానమైన రెండు శ్రేణుల పరిమాణాలను సృష్టించండి.
  2. శ్రేణిని 1 సూచిక నుండి శ్రేణి యొక్క పొడవు వరకు ప్రయాణించండి. మునుపటి సూచిక వద్ద ప్రీఅర్రేలో నిల్వ చేయబడిన ప్రస్తుత మూలకం మరియు మూలకం యొక్క జిసిడిని కనుగొని, ప్రీఅరేలో ప్రస్తుత సూచిక వద్ద నిల్వ చేయండి.
  3. శ్రేణిని కుడి నుండి ఎడమకు ప్రయాణించి, ప్రత్యయంఅరే మూలకం యొక్క జిసిడిని మరియు ఇచ్చిన శ్రేణి మూలకాన్ని కనుగొని, జిసిడిని అరే అనే ప్రత్యయంలోకి నిల్వ చేయండి.
  4. ఇచ్చిన ప్రతి ప్రశ్నకు, ఎడమ పరిధి 0 కి సమానంగా ఉంటే, అప్పుడు ప్రత్యయం అర్రే యొక్క విలువను తిరిగి ఇవ్వండి [కుడి + 1].
  5. కుడి విలువ n - 1 కు సమానంగా ఉంటే, ప్రీఅర్రే యొక్క విలువను తిరిగి ఇవ్వండి [ఎడమ - 1].
  6. ప్రీఅర్రే [ఎడమ -1] మరియు అరే [ప్రత్యయం [కుడి + 1] యొక్క జిసిడి విలువను తిరిగి ఇవ్వండి.

వివరణ

సమాధానం ఇవ్వడానికి పూర్ణాంకాలు మరియు ప్రశ్నల శ్రేణి ఇవ్వబడింది. మేము తెలుసుకోవడానికి అడిగారు గొప్ప సాధారణ విభజన ప్రశ్న యొక్క ఇచ్చిన పరిధిలోని అన్ని పూర్ణాంకాలు మినహా సంఖ్యల. పొడవు 0 యొక్క శ్రేణిలో మనకు 1 నుండి 5 పరిధిని ఇస్తే, దీని అర్ధం అర్రే [0] మరియు అర్రే [1] మినహా అన్ని పూర్ణాంకాల యొక్క గొప్ప సాధారణ విభజనను మనం కనుగొనవలసి ఉంటుంది. ఎడమ మరియు కుడి శ్రేణిని కలిగి ఉన్న ప్రశ్న ఇవ్వబడింది. ఈ పరిధిలో వచ్చే పూర్ణాంకాలను మనం వదిలివేయాలి.

మేము శ్రేణిని దాటబోతున్నాము, కానీ దీనికి ముందు ఇచ్చిన శ్రేణి యొక్క మొదటి మూలకాన్ని ప్రీఅరే యొక్క మొదటి మూలకానికి కాపీ చేయండి. ఆ తరువాత శ్రేణి ఎడమ నుండి కుడికి ప్రయాణించండి. ఈ సమయంలో మేము ప్రీఅర్రే మరియు ప్రత్యయంఅరేను నిర్మిస్తాము. ప్రీఅర్రే కోసం ప్రస్తుత ఇండెక్స్ వద్ద అసలు ఇన్పుట్ శ్రేణిలో మూలకం యొక్క గ్రేటెస్ట్ కామన్ డివైజర్ మరియు ప్రీఅరేలో మునుపటి ఇండెక్స్ వద్ద ఎలిమెంట్‌ను కనుగొనండి. ఈ సంఖ్యల యొక్క ఈ జిసిడిని ప్రీఅరే మూలకంలో నిల్వ చేయండి. శ్రేణి యొక్క ట్రావెర్సల్ తరువాత, అర్రే అనే ప్రత్యయం నిర్మించండి. దాని కోసం, అరే అనే ప్రత్యయం యొక్క చివరి మూలకం స్థానంలో. ఇచ్చిన శ్రేణి మూలకం యొక్క శ్రేణి యొక్క చివరి మూలకాన్ని కాపీ చేయండి. ఆ తరువాత మేము ప్రీఅర్రే కోసం అనుసరించే విధానాన్ని అనుసరిస్తాము కాని శ్రేణి యొక్క కుడి నుండి ఎడమకు.

ఇచ్చిన పరిధి యొక్క ప్రతి ప్రశ్నకు, ఇచ్చిన ఎడమ పరిధి 0 కి సమానంగా ఉందో లేదో తనిఖీ చేయండి. ఆ విధంగా అర్రే [కుడి + 1] ప్రత్యయం విలువను తిరిగి ఇవ్వండి. కుడి విలువ శ్రేణి యొక్క పొడవుకు సమానంగా ఉందో లేదో తనిఖీ చేయండి. అప్పుడు ప్రీఅర్రే యొక్క విలువను తిరిగి ఇవ్వండి [ఎడమ -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”అనేది ఇన్పుట్ శ్రేణిలోని మూలకాల సంఖ్య. పై) ప్రీఅర్రే మరియు ప్రత్యయంఅరే నిర్మాణానికి సమయం అవసరం. అప్పుడు O (Qlog n) ప్రశ్నలకు సమాధానం ఇవ్వడానికి సమయం అవసరం ఎందుకంటే ప్రతి ప్రశ్నకు సమాధానం ఇవ్వడానికి మేము రెండు సంఖ్యల యొక్క జిసిడిని కనుగొంటాము, ఇది మాకు లాగ్ n ఖర్చు అవుతుంది, ఇక్కడ n సంఖ్య మరియు లాగ్ బేస్ 2 తో ఉంటుంది.

అంతరిక్ష సంక్లిష్టత

ఇచ్చిన పరిధిలోని అంశాలు మినహా శ్రేణి యొక్క అన్ని సంఖ్యల యొక్క GCD కోసం ప్రశ్నలను పరిష్కరించడానికి స్థలం సంక్లిష్టత పై) (ఇక్కడ “ఎన్” ప్రీఅర్రే మరియు ప్రత్యయంఅర్రేలను నిల్వ చేయడానికి శ్రేణిలోని మూలకాల సంఖ్య.