সমস্ত অদ্ভুত দৈর্ঘ্যের সুবারারি লেটকোড সমাধানের যোগফল


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় লিঙ্কডইন
বিন্যাস

সমস্যা বিবৃতি

এই সমস্যায় ইতিবাচক পূর্ণসংখ্যার একটি অ্যারে দেওয়া হয়। আমাদের একটি একক পূর্ণসংখ্যার গণনা করতে হবে এবং প্রদত্ত অ্যারের সমস্ত সম্ভাব্য বিজোড় দৈর্ঘ্যের সাবহারির যোগফলটি দিতে হবে। একটি সুব্রয় হল এর একটি সংলগ্ন উপসাগর বিন্যাস.

উদাহরণ

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 (অ্যারের আকার)
৩. এই লুপের ভিতরে, রান করুন লুপ i = 0 থেকে i = n-len পর্যন্ত সাববারির অবস্থান শুরু করার জন্য।
৪) উপরের লুপের অভ্যন্তরে, এই সাববারির জন্য একটি লুপ চালান যার সূচকটি 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

জটিলতা বিশ্লেষণের যোগফলের জন্য সমস্ত অদ্ভুত দৈর্ঘ্যের সুবারাইস লেটকোড সমাধান

সময় জটিলতা

ও (এন ^ 3): আমরা নেস্টেড আকারে তিনটি লুপ ব্যবহার করেছি যেখানে প্রতিটি লুপ নিম্নলিখিত সময় চলমান থাকে:
প্রথম লুপটি n / 2 বার চলছে।
দ্বিতীয় লুপ চলছে (এন-লেন) সময়, যেখানে লেন 1,3,4,…।
তৃতীয় লুপ চলছে লেন বার।
মোট সময় হবে (n / 2) * (n-লেন)*লেন। সুতরাং সময়ের জটিলতার উপরের সীমাটি হবে O (n ^ 3) যেখানে n প্রদত্ত অ্যারের আকার n

স্পেস জটিলতা ity 

ও (1): স্থান জটিলতা ধ্রুবক।

পদ্ধতির (সময় অনুকূলিত)

যেহেতু আমরা দেখতে পাচ্ছি যে উপরের ব্রুট ফোর্স সলিউশনটিতে ও (এন ^ 3) সময় জটিলতা রয়েছে। আমরা এটি হ্রাস করতে পারি কারণ উপরোক্ত পদ্ধতির ক্ষেত্রে আমরা বিভিন্ন সাবহারির জন্য একই উপাদানটি একাধিকবার যুক্ত করছি। যদি কোনওভাবে আমরা জানতে পারি যে কোনও নির্দিষ্ট উপাদানকে কতবার যুক্ত করা হয় বা মোট যোগফলে যোগ করা উচিত, তবে আমরা সময়ের জটিলতা O (n ^ 3) থেকে O (n) এ হ্রাস করতে পারি।

আমরা বিশ্লেষণ করতে পারি যে আমরা যদি সমস্ত সাবহারে (এমনকি এবং বিজোড় দৈর্ঘ্য) গ্রহণ করি, তবে সেই ক্ষেত্রে সূচীতে একটি নির্দিষ্ট উপাদান আমার সমস্ত সাবহারে ঘটবে যার সূচনা সূচক i এর সমান থেকে কম, এবং সমাপ্তি সূচক i এর সমান থেকে বড় হবে ।

অতএব আমরা বলতে পারি যে এয়ার [i] (0-সূচীকৃত) সমেত যে সমস্ত সাবহারিগুলির মোট সংখ্যা (i + 1) * (এনআই) এর সমান হবে।
এই মানটি x হতে দিন।
এর মধ্যে (x + 1) / 2 টি বিজোড় দৈর্ঘ্যের সাববারাই রয়েছে যার মধ্যে আরআর রয়েছে [i]।
এবং এক্স / 2 এমনকি দৈর্ঘ্যের সাবারিগুলি যা আরআর [i] ধারণ করে।
সুতরাং একটি [i] আমাদের সমাধানের মোট যোগফলের (x + 1) / 2 বার অবদান রাখবে।

আমরা এটি একটি সাধারণ উদাহরণ দিয়ে দেখতে পারি:

আসুন = [1, 2, 3, 4, 5]

সমস্ত অদ্ভুত দৈর্ঘ্যের সুবারারি লেটকোড সমাধানের যোগফল

অতএব বিজোড় subarrays = arr [i] * ((আমি + 1) * (এনআই) +1) / 2 এ প্রতিটি উপাদানসমূহের অবদান [i] contribution
এটি একটি একক লুপ ব্যবহার করে করা যেতে পারে এবং তাই এই সমাধানের সময় জটিলতা রৈখিক হবে be

সমস্ত বিজোড় দৈর্ঘ্যের সুবারেস লেটকোড সমাধানের যোগফলের জন্য বাস্তবায়ন

সি ++ প্রোগ্রাম

#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

জটিলতা বিশ্লেষণের যোগফলের জন্য সমস্ত অদ্ভুত দৈর্ঘ্যের সুবারাইস লেটকোড সমাধান

সময় জটিলতা

চালু) : যেহেতু আমরা অ্যারের প্রতিটি উপাদানকে কেবল একবার অতিক্রম করেছি, সুতরাং সময়ের জটিলতা ও (এন) হবে। যেখানে এন প্রদত্ত অ্যারের আকার।

স্পেস জটিলতা ity 

ও (1): আমরা কোনও অতিরিক্ত মেমরি ব্যবহার করি নি, তাই স্পেস জটিলতা স্থির থাকবে।