తేడా శ్రేణి | O (1) లో పరిధి నవీకరణ ప్రశ్న


కఠినత స్థాయి హార్డ్
తరచుగా అడుగుతుంది ఆర్సెసియం కోడ్‌నేషన్ డైరెక్టి Expedia ద్వారా గూగుల్ క్వాల్కమ్
అర్రే ప్రశ్న సమస్య

మీకు ఇవ్వబడింది పూర్ణ సంఖ్య అమరిక మరియు రెండు రకాల ప్రశ్నలు, ఒకటి ఇచ్చిన సంఖ్యను ఒక పరిధిలో మరియు మరొకటి మొత్తం శ్రేణిని ముద్రించడం. సమస్య “తేడా శ్రేణి | O (1) ”లోని శ్రేణి నవీకరణ ప్రశ్న O (1) లో శ్రేణి నవీకరణలను నిర్వహించడానికి మాకు అవసరం.

ఉదాహరణ

arr[] = {20, 30, 25, 50}

Update(0, 1, 10)

print()

update(0, 2, 20)

update(2, 3, 30)

print()
(30 40 25 50) (50 60 75 80)

వివరణ

10 20 మరియు 30 కి జోడించబడతాయి, కాబట్టి శ్రేణి {30, 40, 25, 50 become అవుతుంది

అప్పుడు మేము మొత్తం శ్రేణిని ప్రింట్ చేస్తాము.

20 30, 40 మరియు 25 కి జోడించబడుతుంది, కాబట్టి శ్రేణి {50, 60, 45, 50 become అవుతుంది

10 45 మరియు 50 కి జోడించబడతాయి, కాబట్టి శ్రేణి {50, 60, 75, 80 become అవుతుంది

అప్పుడు మళ్ళీ మేము మొత్తం శ్రేణిని ప్రింట్ చేస్తాము.

ప్రశ్నలను ప్రదర్శించిన తర్వాత రెండు సెట్ల విలువలు ముద్రించబడతాయి.

తేడా శ్రేణి | O (1) లో పరిధి నవీకరణ ప్రశ్న

 

తేడా శ్రేణి కోసం అల్గోరిథం

  1. ఇచ్చిన శ్రేణికి సమానమైన శ్రేణిని సృష్టించండి.
  2. ఇచ్చిన సూచిక యొక్క మొదటి మూలకం వలె మొదటి సూచికను ప్రారంభించండి మరియు చివరి సూచిక 0 తో ప్రారంభించండి. మరియు అన్ని ఇతర సూచికలు ప్రస్తుత మరియు మునుపటి మూలకం యొక్క వ్యత్యాసంతో నిండి ఉంటాయి.
  3. ప్రతి నవీకరణ ప్రశ్నకు, సృష్టించిన శ్రేణి యొక్క ఎడమ సూచికకు X విలువను జోడించి, సృష్టించిన శ్రేణి యొక్క కుడి సూచిక నుండి X ను తీసివేయండి.
  4. ప్రతి ముద్రణ ప్రశ్నకు, మొదట మేము A [i] = D [i] + A [i-1] సూత్రాన్ని ఉపయోగించి ఇన్‌పుట్ శ్రేణిని నింపుతాము. అప్పుడు విలువలను ముద్రించండి.

వివరణ

శ్రేణి మరియు సంఖ్య మరియు రెండు రకాల ప్రశ్నలు ఇవ్వబడ్డాయి. కాబట్టి మనం రెండు రకాల ప్రశ్నలను చేయవలసి ఉంటుంది. మనకు ఒక సంఖ్య X తో పాటు పరిధిని సూచించే రెండు సంఖ్యలు ఉంటాయి. కాబట్టి, ఇచ్చిన పరిధి మధ్య ఉన్న అన్ని సూచికలకు X సంఖ్యను జోడించడం మా పని. ఒక పద్ధతి అమాయక విధానాన్ని ఉపయోగించడం. దాని కోసం, మేము విలువలను నవీకరించాల్సిన ప్రతిసారీ ఇచ్చిన శ్రేణిని దాటండి.

మంచి పరిష్కారం ఇక్కడ చర్చించబడింది, ఇది వ్యత్యాసాన్ని నిల్వ చేసే అదనపు శ్రేణిని సృష్టించడం. అందుకే దీనిని తేడా శ్రేణి అని పిలుస్తున్నారు. మొదట, తేడా శ్రేణి యొక్క మొదటి మూలకాన్ని ఇన్‌పుట్ శ్రేణి యొక్క మొదటి మూలకంగా ప్రారంభించండి. అప్పుడు తేడా శ్రేణి యొక్క చివరి మూలకాన్ని 0 కి కేటాయించండి. ఆ తరువాత, మేము శ్రేణి గుండా ప్రయాణించి, ప్రస్తుత విలువ మరియు మునుపటి విలువ యొక్క వ్యత్యాసాన్ని ప్రస్తుత శ్రేణి వద్ద వ్యత్యాస శ్రేణిలో నిల్వ చేయబోతున్నాము.

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

కోడ్

తేడా శ్రేణి కోసం C ++ లో అమలు

#include<iostream>

using namespace std;

void buildArray(int arr[], int dummyArray[], int n)
{
    dummyArray[0] = arr[0];
    dummyArray[n] = 0;
    for (int i = 1; i < n; i++)
        dummyArray[i] = arr[i] - arr[i - 1];
}

static void update(int dummyArray[], int l, int r, int x)
{
    dummyArray[l] += x;
    dummyArray[r + 1] -= x;
}

void printArray(int arr[], int dummyArray[], int n)
{
    for (int i = 0; i <n; i++)
    {

        if (i == 0)
            arr[i] = dummyArray[i];
        else
            arr[i] = dummyArray[i] + arr[i - 1];

        cout<<arr[i] << " ";
    }

    cout<<endl;
}

int main()
{
    int arr[] = {20,30,25,50};
    int n = sizeof(arr)/sizeof(arr[0]);

    int dummyArray[n + 1];
    buildArray(arr, dummyArray, n);

    update(dummyArray, 0, 1, 10);
    printArray(arr, dummyArray, n);
    update(dummyArray, 0, 2, 20);
    update(dummyArray, 2, 3, 30);

    printArray(arr, dummyArray,n);
    return 0;
}
30 40 25 50
50 60 75 80

తేడా శ్రేణి కోసం జావాలో అమలు

class differenceArray
{
    static void buildArray(int arr[], int dummyArray[])
    {

        int n = arr.length;

        dummyArray[0] = arr[0];
        dummyArray[n] = 0;
        for (int i = 1; i < n; i++)
            dummyArray[i] = arr[i] - arr[i - 1];
    }
    
    static void update(int dummyArray[], int left, int right, int x)
    {
        dummyArray[left] += x;
        dummyArray[right + 1] -= x;
    }
    
    static int printArray(int arr[], int dummyArray[])
    {
        for (int i = 0; i < arr.length; i++)
        {
            if (i == 0)
                arr[i] = dummyArray[i];
            else
                arr[i] = dummyArray[i] + arr[i - 1];

            System.out.print(arr[i] + " ");
        }

        System.out.println();

        return 0;
    }
    
    public static void main(String[] args)
    {
        int arr[] = {20, 30, 25, 50};
        int n = arr.length;
        int dummyArray[] = new int[n + 1];

        buildArray(arr, dummyArray);

        update(dummyArray, 0, 1, 10);
        printArray(arr, dummyArray);
        update(dummyArray, 0, 2, 20);
        update(dummyArray, 2, 3, 30);

        printArray(arr, dummyArray);
    }
}
30 40 25 50
50 60 75 80

సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత

O (q)  (ఇక్కడ  "Q" నవీకరణ ప్రశ్న తీసుకునేటప్పుడు అమలు చేయబడిన ముద్రణ ప్రశ్నల సంఖ్య O (1) సమయం.

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

పై) (ఇక్కడ  “N” శ్రేణిలోని మూలకాల సంఖ్య. మేము అదనపు వ్యత్యాస శ్రేణిని సృష్టించినందున, మాకు సరళ స్థల సంక్లిష్టత ఉంది.