এই নিবন্ধে, আমরা C++ ব্যবহার করে K-এর থেকে কম যোগফলের সাবয়ারের সংখ্যা খুঁজে বের করব। এই সমস্যায়, আমাদের একটি অ্যারে অ্যারে[] এবং একটি পূর্ণসংখ্যা K আছে। তাই এখন আমাদের এমন সাবয়ারে খুঁজে বের করতে হবে যার যোগফল K-এর থেকে কম। এখানে উদাহরণ −
Input : arr[] = {1, 11, 2, 3, 15}
K = 10
Output : 4
{1}, {2}, {3} and {2, 3} সমাধান খোঁজার পদ্ধতি
এখন আমরা প্রদত্ত সমস্যাটি সমাধান করতে দুটি ভিন্ন পদ্ধতি ব্যবহার করব −
ব্রুট ফোর্স
এই পদ্ধতিতে, আমরা সমস্ত সাবয়ারের মাধ্যমে পুনরাবৃত্তি করব এবং তাদের যোগফল গণনা করব এবং আমাদের উত্তর বৃদ্ধি করতে যোগফল k-এর থেকে কম হলে k-এর সাথে তুলনা করব।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int main(){
int arr[] = {1, 11, 2, 3, 15}; // given array
int k = 10; // given k
int size = sizeof(arr) / sizeof(int); // size of our array.
int ans = 0; // counter variable.
for(int i = 0; i < size; i++){ // outer loop.
int sum = 0;
for(int j = i; j < size; j++){ // inner loop.
sum = sum + arr[j];
if(sum < k) // comparing with k.
ans++; // incrementing our ans if sum is less than k.
}
}
cout << ans << "\n";
return 0;
} আউটপুট
4
যাইহোক, এই পদ্ধতিটি খুব ভাল নয় কারণ এটির সময় জটিলতা খুব বেশি O(N*N) , যেখানে n হল আমাদের অ্যারের আকার।
আমরা স্লাইডিং উইন্ডো পদ্ধতি ব্যবহার করে একটি বিকল্প সমাধান দেখব (যা আমাদের প্রোগ্রামের সময় জটিলতা কমাতে সাহায্য করবে)।
দক্ষ পদ্ধতি
ব্রুট ফোর্স থেকে ভিন্ন , আমরা সব subarray মাধ্যমে যাচ্ছে না. পরিবর্তে, আমরা তখনই অতিক্রম করব যখন একটি সাবয়ারের যোগফল k ছাড়িয়ে যাবে এবং আমাদের বাম সীমানাকে আমাদের ডান সীমানা পর্যন্ত নিয়ে যাবে এবং পুরো অ্যারেটি অতিক্রম না করা পর্যন্ত পুনরাবৃত্তি করতে থাকবে৷
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int main(){
int arr[] = {1, 11, 2, 3, 15}; // given array
int k = 10; // given k
int size = sizeof(arr) / sizeof(int); // size of our array.
int ans = 0; // counter variable.
int start = 0; // left border.
int end = 0; // right border.
int sum = 0;
while(end < size && start < size){ // till the whole array is traversed.
while(sum >= k && start < end){
sum = sum - arr[start];
start++;
}
if(end >= start)
ans = ans + end - start;
sum += arr[end];
end++;
}
cout << ans << "\n";
return 0;
} আউটপুট
4
আমরা স্লাইডিং উইন্ডো টেকনিক ব্যবহার করি এই পদ্ধতিতে বড় সীমাবদ্ধতার জন্য আমাদের প্রোগ্রামকে দ্রুত বা সময়-দক্ষ করার জন্য।
উপরের কোডের ব্যাখ্যা
এই পদ্ধতিতে, আমরা সাধারণত আমাদের যোগফল k-এর থেকে কম না হওয়া পর্যন্ত অতিক্রম করছি এবং সেই অনুযায়ী আমাদের উত্তর বৃদ্ধি করছি এখন কোডের গুরুত্বপূর্ণ পরিবর্তন যা ঘটে যখন যোগফল k-এর সমান বা বড় হয়। এই অবস্থায়, আমরা আমাদের বাম সীমানাকে আমাদের ডান সীমানা থেকে ছোট করতে শুরু করি বা যতক্ষণ না যোগফল k এর সমান বা বড় হয়। আমরা আরও প্রক্রিয়া করার সাথে সাথে এটি গঠিত হতে পারে এমন অন্যান্য সাব্যারেগুলির মধ্য দিয়ে অতিক্রম করে। এই নতুন সাবয়ারে যার যোগফল k এর থেকে কম তা আমাদের উত্তরে যোগ করা হয়েছে, তাই আমাদের উত্তর বৃদ্ধি করা হয়েছে।
এই পদ্ধতিটি আগের ব্রুট ফোর্স এর তুলনায় খুবই দক্ষ আমরা প্রয়োগ করেছি কারণ এর সময় জটিলতা হল O(N) , যেখানে N হল আমাদের অ্যারের আকার।
উপসংহার
এই নিবন্ধে, আমরা স্লাইডিং উইন্ডো টেকনিক ব্যবহার করে k এর থেকে কম যোগফল সহ সাবয়ারের সংখ্যা খুঁজে পেতে একটি সমস্যার সমাধান করি। . আমরা এই সমস্যার জন্য C++ প্রোগ্রাম এবং সম্পূর্ণ পদ্ধতি ( স্বাভাবিক এবং দক্ষ) শিখেছি যার মাধ্যমে আমরা এই সমস্যার সমাধান করেছি। আমরা অন্যান্য ভাষা যেমন সি, জাভা, পাইথন এবং অন্যান্য ভাষায় একই প্রোগ্রাম লিখতে পারি। আশা করি আপনি এই নিবন্ধটি সহায়ক বলে মনে করেন৷
