నవీకరణలు లేకుండా పరిధి మొత్తం ప్రశ్నలు


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది నలుపు రాయి GE హెల్త్ మూన్‌ఫ్రాగ్ ల్యాబ్స్ Synopsys టాక్సీ 4 సురే Twilio
అర్రే లార్సెన్ & టౌబ్రో ప్రశ్న సమస్య

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

“నవీకరణలు లేని శ్రేణి మొత్తం ప్రశ్నలు” సమస్య మీకు ఉందని పేర్కొంది అమరిక of పూర్ణాంకాల మరియు ఒక పరిధి. ఇచ్చిన స్టేట్మెంట్‌లోని అన్ని మూలకాల మొత్తాన్ని తెలుసుకోవడానికి సమస్య స్టేట్‌మెంట్ అడుగుతుంది.

ఉదాహరణ

arr[]={10, 9, 8, 7, 6}

Query: {(0, 4), (1, 3)}
40 24

వివరణ

పరిధి (0, 4) మధ్య ఉన్న అన్ని సంఖ్యల మొత్తం 40 మరియు పరిధి (1, 3) మధ్య ఉన్న అన్ని సంఖ్యల మొత్తం 24 గా ఉంటుంది.

నవీకరణలు లేకుండా పరిధి మొత్తం ప్రశ్నలు

 

అల్గారిథం

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

వివరణ

మేము పూర్ణాంకం మరియు శ్రేణి యొక్క శ్రేణిని ఇచ్చాము, ప్రతి ప్రశ్నకు ఇచ్చిన పరిధిలోని అన్ని మూలకాల మొత్తాన్ని కనుగొనమని అడిగారు. ప్రతి ప్రశ్నలు ఒక శ్రేణి యొక్క ప్రారంభ మరియు ముగింపు బిందువుగా ఉంటాయి. ఈ ప్రశ్నలో ఎటువంటి నవీకరణ ప్రశ్న ఉండదు. అంటే ప్రశ్న సమాధానాన్ని కనుగొనేటప్పుడు ఏదైనా విషయాలను నవీకరించాల్సిన అవసరం లేదు. మేము ఇచ్చిన శ్రేణిని నిర్మిస్తాము, తద్వారా 0 సూచిక నుండి ప్రస్తుత సూచిక వరకు ఉన్న అన్ని మూలకాల మొత్తం అంతర్నిర్మిత శ్రేణి యొక్క ith స్థానంలో ఉంటుంది. ఈ విధంగా, ప్రతి ప్రశ్న O (1) లో పరిష్కరించబడుతుంది, O (n) యొక్క అదనపు స్థలం ఉంటుంది.

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

మేము ఏదైనా పరిధిని కలిగి ఉన్న ప్రశ్నను అందుకున్నప్పుడు, మరియు శ్రేణి యొక్క ఎడమ లేదా ప్రారంభ స్థానం 0 కి సమానమని మేము కనుగొంటే, మేము సమ్అరే యొక్క విలువను తిరిగి ఇస్తాము [కుడి] అది మేము పైన చర్చించినది, ఎడమ పరిధి 0 కి సమానం కాదు మేము sumArray [right] మరియు sumArray [left-1] యొక్క వ్యత్యాసాన్ని తిరిగి ఇస్తాము. వీటికి అవసరమైన సమాధానాలు ఉంటాయి. ఈ విధానం మనం ఉపయోగించే సులభమైన మార్గాలలో ఒకటి డైనమిక్ ప్రోగ్రామింగ్.

కోడ్

నవీకరణలు లేకుండా శ్రేణి మొత్తం ప్రశ్నలకు C ++ కోడ్

#include<iostream>

using namespace std;

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

int solveQuery(int left, int right, int sumArray[])
{
    if (left == 0)
        return sumArray[right];

    return sumArray[right] - sumArray[left -1];
}

int main()
{
    int arr[] = {10,9,8,7,6};
    int n = sizeof(arr)/sizeof(arr[0]);

    int sumArray[n];

    buildSumArray(arr, n, sumArray);

    cout << solveQuery(0, 4, sumArray) << endl;
    cout << solveQuery(1, 3, sumArray) << endl;

    return 0;
}
40
24

నవీకరణలు లేకుండా శ్రేణి మొత్తం ప్రశ్నల కోసం జావా కోడ్

class RangeQueriesSum
{
    public static void buildSumArray(int arr[], int n, int sumArray[])
    {
        sumArray[0] = arr[0];
        for (int i = 1; i < n; i++)
            sumArray[i] = arr[i] + sumArray[i - 1];
    }

    public static int solveQuery(int left, int right, int sumArray[])
    {
        if (left == 0)
            return sumArray[right];

        return sumArray[right] - sumArray[left -1];
    }

    public static void main(String[] args)
    {
        int arr[] = {10,9,8,7,6};
        int n = arr.length;

        int sumArray[] = new int[n];

        buildSumArray(arr, n, sumArray);
        System.out.println(solveQuery(0, 4, sumArray));
        System.out.println(solveQuery(1, 3, sumArray));
    }
}
40
24

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

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

O (N + Q),  ఎందుకంటే సమ్‌అర్రేను లెక్కించడానికి మాకు O (N) అవసరం మరియు ప్రతి ప్రశ్నకు O (1) సమయం అవసరం.

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

ఇక్కడ ఇచ్చిన విధానంలో, 0 నుండి i వరకు మూలకాల మొత్తాన్ని నిల్వ చేయడానికి మేము క్రొత్త శ్రేణి సమ్అరేను సృష్టించాము. అందువలన ఈ విధానం అవసరం పై) స్థలం. కానీ మేము అసలు శ్రేణిని కూడా సవరించవచ్చు. అప్పుడు స్థల సంక్లిష్టత స్థిరంగా ఉంటుంది.