అన్ని బేసి పొడవు సబ్రేస్ లీట్‌కోడ్ సొల్యూషన్ మొత్తం


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది లింక్డ్ఇన్
అర్రే

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

ఈ సమస్యలో సానుకూల పూర్ణాంకాల శ్రేణి ఇవ్వబడుతుంది. మేము ఇచ్చిన పూర్ణాంకాన్ని లెక్కించాలి మరియు తిరిగి ఇవ్వాలి, ఇచ్చిన శ్రేణి యొక్క అన్ని బేసి పొడవు సబ్‌రేల మొత్తం. ఒక సబ్‌రే అనేది ఒక తరువాతి పరిణామం అమరిక.

ఉదాహరణ

arr = [1,4,2,5,3]
58

వివరణ:

అర్ యొక్క బేసి-పొడవు సబ్‌రేలు మరియు వాటి మొత్తాలు:
[1] = 1, [4] = 4, [2] = 2, [5] = 5, [3] = 3, [1,4,2] = 7, [4,2,5] = 11, [2,5,3] = 10, [1,4,2,5,3] = 15
ఇవన్నీ కలిపితే మనకు 1 + 4 + 2 + 5 + 3 + 7 + 11 + 10 + 15 = 58 లభిస్తుంది

arr = [1,2]
3

వివరణ:

బేసి పొడవు యొక్క 2 సబ్‌రేలు మాత్రమే ఉన్నాయి, [1] మరియు [2]. వారి మొత్తం 3.

అప్రోచ్ (బ్రూట్ ఫోర్స్)

బ్రూట్ ఫోర్స్ ద్వారా ఈ సమస్యను పరిష్కరించడానికి, మేము అన్ని బేసి పొడవు సబ్‌రేల కోసం వెళ్లి మొత్తం మొత్తాన్ని లెక్కించి తిరిగి ఇవ్వాల్సిన సమస్య నుండి చూడటం చాలా సులభం.
సాధారణ దశలను అనుసరించడం ద్వారా మేము దీన్ని అమలు చేయవచ్చు:

1. వేరియబుల్ సృష్టించండి మొత్తం మొత్తం మొత్తాన్ని నిల్వ చేయడానికి.
2. ప్రారంభమయ్యే అన్ని బేసి పొడవు సబ్‌రేల కోసం లూప్ కోసం రన్ చేయండి లెన్= 1 మరియు విలువను 2 పెంచేటప్పుడు ఉంచండి లెన్ <= n (శ్రేణి యొక్క పరిమాణం).
3. ఈ లూప్ లోపల, a ను అమలు చేయండి లూప్ i = 0 నుండి i = n-len వరకు సబ్‌రే యొక్క స్థానం ప్రారంభించడానికి.
4. పై లూప్ లోపల, ఈ సబ్‌రే కోసం లూప్‌ను రన్ చేయండి, దీని సూచిక i నుండి మొదలై i + వద్ద ముగుస్తుందిలెన్-1 మరియు ఈ సబ్‌రే యొక్క అన్ని అంశాలను జోడించండి.
5. చివరికి తిరిగి మొత్తం.

అన్ని బేసి పొడవు సబ్రేస్ లీట్‌కోడ్ సొల్యూషన్ మొత్తానికి అమలు

సి ++ ప్రోగ్రామ్

#include <bits/stdc++.h>
using namespace std;

int sumOddLengthSubarrays(vector<int>& arr) 
{
    int sum=0;
    int n=arr.size();

    for(int len=1;len<=n;len+=2)
        for(int i=0;i<n-len+1;i++)
            for(int j=i;j<i+len;j++) 
                sum+=arr[j];
    
    return sum;
}

int main() 
{
    vector<int> arr = {1,4,2,5,3};
  
  cout<<sumOddLengthSubarrays(arr)<<endl;

  return 0; 
}
58

జావా ప్రోగ్రామ్

#include <bits/stdc++.h>
using namespace std;

int sumOddLengthSubarrays(vector<int>& arr) 
{
    int sum=0;
    int n=arr.size();

    for(int len=1;len<=n;len+=2)
        for(int i=0;i<n-len+1;i++)
            for(int j=i;j<i+len;j++) 
                sum+=arr[j];
    
    return sum;
}

int main() 
{
    vector<int> arr = {1,4,2,5,3};
  
  cout<<sumOddLengthSubarrays(arr)<<endl;

  return 0; 
}
58

అన్ని ఆడ్ లెంగ్త్ సబ్‌రేస్ లీట్‌కోడ్ సొల్యూషన్ మొత్తానికి సంక్లిష్టత విశ్లేషణ

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

O (n ^ 3): మేము మూడు లూప్‌లను సమూహ రూపంలో ఉపయోగించాము, ఇక్కడ ప్రతి లూప్ క్రింది సార్లు నడుస్తుంది:
మొదటి లూప్ n / 2 సార్లు నడుస్తోంది.
రెండవ లూప్ నడుస్తోంది (n-లెన్) సార్లు, ఎక్కడ లెన్ 1,3,4,….
మూడవ లూప్ నడుస్తోంది లెన్ సార్లు.
మొత్తం సమయం (n / 2) * (n-లెన్)*లెన్. అందువల్ల సమయ సంక్లిష్టత యొక్క ఎగువ బంధం O (n ^ 3) ఇక్కడ n అనేది ఇచ్చిన శ్రేణి యొక్క పరిమాణం.

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

ఓ (1): స్థల సంక్లిష్టత స్థిరంగా ఉంటుంది.

అప్రోచ్ (సమయం ఆప్టిమైజ్ చేయబడింది)

పై బ్రూట్ ఫోర్స్ ద్రావణంలో O (n ^ 3) సమయ సంక్లిష్టత ఉందని మనం చూడవచ్చు. మేము దీన్ని కనిష్టీకరించవచ్చు ఎందుకంటే పై విధానంలో మేము ఒకే మూలకాన్ని వేర్వేరు సబ్‌రేల కోసం అనేకసార్లు జోడిస్తున్నాము. ఒక నిర్దిష్ట మూలకం ఎన్నిసార్లు జోడించబడిందో లేదా మొత్తం మొత్తానికి జోడించబడాలని మనకు తెలిస్తే, అప్పుడు మేము O (n ^ 3) నుండి O (n) కు సమయ సంక్లిష్టతను తగ్గించవచ్చు.

మేము అన్ని సబ్‌రేలను (సరి మరియు బేసి పొడవు) తీసుకుంటే, ఆ సందర్భంలో ఇండెక్స్ వద్ద ఒక నిర్దిష్ట మూలకం అన్ని సబ్‌రేర్‌లలో సంభవిస్తుంది, దీని ప్రారంభ సూచిక నాకు సమానమైన దానికంటే తక్కువ, మరియు ముగింపు సూచిక i కి సమానం కంటే ఎక్కువ .

అందువల్ల అర్ర్ [i] (0-ఇండెక్స్డ్) కలిగి ఉన్న మొత్తం సబ్‌రేల సంఖ్య (i + 1) * (ని) కు సమానంగా ఉంటుందని మేము చెప్పగలం.
ఈ విలువ x గా ఉండనివ్వండి.
వీటిలో (x + 1) / 2 బేసి పొడవు సబ్‌రేలు ఉన్నాయి, ఇందులో అర్ర్ [i] ఉంటుంది.
మరియు అర్ర్ [i] ను కలిగి ఉన్న x / 2 సరి పొడవు సబ్‌రేలు.
అందువల్ల మా పరిష్కారంలో మొత్తం మొత్తంలో [x] (x + 1) / 2 రెట్లు దోహదం చేస్తుంది.

మేము దీనిని సరళమైన ఉదాహరణతో చూడవచ్చు:

Arr = [1, 2, 3, 4, 5]

అన్ని బేసి పొడవు సబ్రేస్ లీట్‌కోడ్ సొల్యూషన్ మొత్తం

అందువల్ల బేసి సబ్‌రేస్‌లలో అర్ర్ [i] యొక్క సహకారం = అర్ [i] * ((i + 1) * (ని) +1) / 2.
ఇది ఒకే లూప్ ఉపయోగించి చేయవచ్చు మరియు అందువల్ల ఈ పరిష్కారం యొక్క సమయం సంక్లిష్టత సరళంగా ఉంటుంది.

అన్ని బేసి పొడవు సబ్రేస్ లీట్‌కోడ్ సొల్యూషన్ మొత్తానికి అమలు

సి ++ ప్రోగ్రామ్

#include <bits/stdc++.h>
using namespace std;

int sumOddLengthSubarrays(vector<int>& arr) 
{
    int sum=0;
    int n=arr.size();

    for(int i=0;i<n;i++)
    {
        int contribution= ((i+1)*(n-i) +1)/2;
        sum+= contribution* arr[i];
    }

    return sum;
}

int main() 
{
    vector<int> arr = {1,4,2,5,3};
  
  cout<<sumOddLengthSubarrays(arr)<<endl;

  return 0; 
}
58

జావా ప్రోగ్రామ్

#include <bits/stdc++.h>
using namespace std;

int sumOddLengthSubarrays(vector<int>& arr) 
{
    int sum=0;
    int n=arr.size();

    for(int i=0;i<n;i++)
    {
        int contribution= ((i+1)*(n-i) +1)/2;
        sum+= contribution* arr[i];
    }

    return sum;
}

int main() 
{
    vector<int> arr = {1,4,2,5,3};
  
  cout<<sumOddLengthSubarrays(arr)<<endl;

  return 0; 
}
58

అన్ని ఆడ్ లెంగ్త్ సబ్‌రేస్ లీట్‌కోడ్ సొల్యూషన్ మొత్తానికి సంక్లిష్టత విశ్లేషణ

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

పై) : మేము శ్రేణి యొక్క ప్రతి మూలకాన్ని ఒక్కసారి మాత్రమే దాటినప్పుడు, సమయ సంక్లిష్టత O (n) గా ఉంటుంది. ఇక్కడ n అనేది ఇచ్చిన శ్రేణి యొక్క పరిమాణం.

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

ఓ (1): మేము అదనపు మెమరీని ఉపయోగించలేదు, అందువల్ల స్థల సంక్లిష్టత స్థిరంగా ఉంటుంది.