C++ এ প্রদত্ত যোগফল - (অঋণমূলক সংখ্যা) সহ সাবয়ারে খুঁজুন

এই সমস্যায়, আমাদেরকে একটি অ্যারে দেওয়া হয়েছে অ্যারে [] যা এন পজিটিভ পূর্ণসংখ্যার সমন্বয়ে সংরক্ষিত হয়। আমাদের কাজ হল প্রদত্ত যোগফলের সাথে একটি সাবয়ারে খুঁজে পাওয়া .

সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,

Input : arr[] = {2, 5, 1, 4, 6, 9, 5} sum = 11
Output : subarray = {1, 4, 6}

ব্যাখ্যা −

Subarray sum = 1 + 4 + 6 = 11

সমাধান পদ্ধতি

সমস্যার একটি সহজ সমাধান হল নেস্টেড লুপ ব্যবহার করা। আমরা অ্যারের মাধ্যমে লুপ করব এবং একটি অভ্যন্তরীণ লুপ ব্যবহার করে, আমরা সাবারে খুঁজে পাব। প্রতিটি সাবয়ারের জন্য আমরা সমস্ত উপাদানের যোগফল খুঁজে বের করব এবং প্রদত্ত যোগফল মানের সাথে তুলনা করব। এটি সমান হলে, subarray মুদ্রণ. যদি অ্যারের সমস্ত উপাদান ট্র্যাভার্স করা হয়, তবে এমন কোনও অ্যারে পাওয়া যায় না।

অ্যালগরিদম

• ধাপ 1 − অ্যারের মাধ্যমে লুপ করুন, i -> 0 থেকে (n-1)।

  • পদক্ষেপ 1.1৷ − প্রতিটি উপাদানের জন্য, সম্ভাব্য সকল সাবয়ারের জন্য প্রতিটি সাবয়ারের সমষ্টি খুঁজুন।

  • পদক্ষেপ 1.2৷ − যদি বর্তমান সমষ্টি অ্যারের উপাদানগুলির যোগফল প্রদত্ত সাবয়েরের সমান হয়, তাহলে সাব্যারে মুদ্রণ করুন৷

• ধাপ 2 − যদি অ্যারের সমস্ত উপাদান ট্রাভার্স করা হয় এবং কোন সাব্যারে পাওয়া না যায়। প্রিন্ট করুন "প্রদত্ত যোগফলের সাথে কোন সাবয়ারে পাওয়া যায়নি!"।

উদাহরণ

আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম

#include <bits/stdc++.h>
using namespace std;
void printSubArray(int arr[], int i, int j){
   cout<<"{";
      for(; i < j; i++)
      cout<<arr[i]<<" ";
   cout<<"}";
}
int findSubArrayWithSum(int arr[], int n, int sum) {
   int currSum;
   for (int i = 0; i < n; i++) {
      currSum = arr[i];
      for (int j = i + 1; j <= n; j++) {
         if (currSum == sum) {
            cout<<"Subarray with given sum : ";
            printSumArray(arr, i, j); return 1;
         }
         if (currSum > sum || j == n)
         break;
         currSum = currSum + arr[j];
      }
   }
   cout<<"No subarray found";
   return 0;
}
int main() {
   int arr[] = { 2, 5, 1, 4, 6, 9, 3};
   int n = sizeof(arr) / sizeof(arr[0]);
   int sum = 11;
   findSubArrayWithSum(arr, n, sum);
   return 0;
}

আউটপুট

Subarray with given sum : { 1 4 6 }

সমস্যা সমাধানের জন্য একটি ভাল পদ্ধতি হল স্লাইডিং উইন্ডোর মতো একটি পদ্ধতি ব্যবহার করা কিন্তু এখানে আমাদের একটি পরিবর্তনশীল উইন্ডো থাকবে। আমরা অ্যারের প্রথম উপাদান থেকে শুরু করব, উইন্ডোতে উপাদান যোগ করব যতক্ষণ না যোগফল প্রদত্ত যোগফলের থেকে বড় হয়। যদি এটির থেকে বড় হয়ে যায় তাহলে উপাদানগুলি সরিয়ে ফেলুন যতক্ষণ না এটি আবার যোগফলের চেয়ে কম হয়ে যায়। পুরো অ্যারেটি অতিক্রম না করা পর্যন্ত এই প্রক্রিয়াটি করুন৷

যদি কোনো সময়ে, উইন্ডোর যোগফল প্রদত্ত যোগফলের সমান হয়ে যায়, তাহলে সাবারে প্রিন্ট করুন। এবং যদি প্রদত্ত যোগফলের সমতুল্য কোনো উইন্ডো পাওয়া যায় না এবং ট্র্যাভার্স করার মতো কোনো উপাদান না থাকে, তাহলে প্রিন্ট করুন "কোন সাব্যারে পাওয়া যায়নি!" .

অ্যালগরিদম

শুরু করুন − windowSum =0, sindex =0, endindex =0

• ধাপ 1 - এন্ডইন্ডেক্স ব্যবহার করে অ্যারে ট্র্যাভার্স করুন।

  • পদক্ষেপ 1.1৷ −উইন্ডোসাম যোগ করে এলিমেন্ট যোগ করে আপডেট করুন যতক্ষণ না windowSum যোগফলের থেকে বড় হয়, যেমন if(windowSum windowSum =windowSum + arr[endIndex]।

  • পদক্ষেপ 1.2৷ − যদি windowSum যোগফলের চেয়ে বড় হয়, তাহলে উপাদানগুলি সরিয়ে উইন্ডোর আকার কমিয়ে দিন যেমন (windowSum windowSum =windowSum - arr[endIndex]।

  • পদক্ষেপ 1.3৷ − যদি windowSum ==যোগফল, প্রিন্ট সাব্যারে।

• ধাপ 2 − যদি অ্যারেটি অতিক্রম করা হয়, তাহলে প্রিন্ট করুন -> 'সম্ভব নয়'।

উদাহরণ

আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম

#include <bits/stdc++.h>
using namespace std;
void printSubArray(int arr[], int i, int j){
   cout<<"{ ";
      for(; i < j; i++)
      cout<<arr[i]<<" ";
   cout<<"}";
}
int findSubArrayWithSum(int arr[], int n, int sum) {
   int windowSum = arr[0], startIndex = 0, endIndex;
   for (endIndex = 1; endIndex <= n; endIndex++) {
      while (windowSum > sum && startIndex < endIndex - 1) {
         windowSum -= arr[startIndex];
         startIndex++;
      }
      if (windowSum == sum) {
         cout << "Subarray with given sum : ";
         printSumArray(arr, startIndex ,endIndex);
         return 1;
      }
      if (endIndex < n)
      windowSum += arr[endIndex];
   }
   cout << "No subarray found";
   return 0;
}
int main() {
   int arr[] = { 2, 5, 1, 4, 6, 9, 3};
   int n = sizeof(arr) / sizeof(arr[0]);
   int sum = 11;
   findSubArrayWithSum(arr, n, sum);
   return 0;
}

আউটপুট

Subarray with given sum : { 1 4 6 }