এই সমস্যায়, আমাদেরকে N পূর্ণসংখ্যার মান এবং N আকারের একটি উইন্ডো সমন্বিত একটি অ্যারে অ্যারে দেওয়া হয়েছে। আমাদের কাজ হল কি আকারের প্রতিটি উইন্ডোতে প্রথম ঋণাত্মক পূর্ণসংখ্যা খুঁজে পাওয়ার জন্য একটি প্রোগ্রাম তৈরি করা . আমরা প্রথম ঋণাত্মক সংখ্যা প্রিন্ট করব যদি এটি বিদ্যমান থাকে অন্যথায় 0 প্রিন্ট করে, কোন নেতিবাচক অস্তিত্ব নেই বোঝায়।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
Input: arr[] = {-2, 2, -1, 4, 3, -6}, k = 2
Output: -2, -1, -1, 0, -6 ব্যাখ্যা −
Size of window k = 2,
{-2, 2}, first negative is -2
{2, -1}, first negative is -1
{-1, 4}, first negative is -1
{4, 3}, first negative is 0 (no negative exists)
{3, -6}, first negative is -6 সমাধান পদ্ধতি
সমস্যা সমাধানের একটি সহজ পদ্ধতি হল অ্যারে arr[] কে অতিক্রম করে k আকারের উইন্ডো তৈরি করা। এবং প্রতিটি উইন্ডোতে প্রথম ঋণাত্মক পূর্ণসংখ্যা খুঁজে বের করুন এবং এটি মুদ্রণ করুন।
সমাধানটি একটি নিষ্পাপ যেটি অপারেশন সম্পাদনের জন্য দুটি নেস্টেড লুপ ব্যবহার করে। তাই সমাধানের সময় জটিলতা হল O(n*k).
ক্রমউদাহরণ
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম
#include <iostream>
using namespace std;
void findFirstNegIntWindowK(int arr[], int n, int k){
bool negFound;
for (int i = 0; i<(n-k+1); i++)
{
negFound = false;
for (int j = 0; j<k; j++)
{
if (arr[i+j] < 0)
{
cout<<arr[i+j]<<"\t";
negFound = true;
break;
}
}
if (!negFound)
cout<<"0\t";
}
}
int main(){
int arr[] = {-2, 2, -1, 4, 3, -6};
int n = sizeof(arr)/sizeof(arr[0]);
int k = 2;
cout<<"First negative integer in each with of size "<<k<<" is \n";
findFirstNegIntWindowK(arr, n, k);
return 0;
} আউটপুট
First negative integer in each with of size 2 is -2 -1 -1 0 -6
সমস্যা সমাধানের আরেকটি পদ্ধতি হল স্লাইডিং উইন্ডো এর অনুরূপ একটি ধারণা ব্যবহার করা . এর জন্য, আমরা একটি ডিকিউ তৈরি করব k আকারের উইন্ডোর সমস্ত উপাদানের জন্য k আকারের (একটি ডবল-এন্ডেড সারি)। আমরা শুরু থেকে অ্যারে অতিক্রম করা শুরু করব এবং k আকারের সারিতে উপাদানটি পূরণ করব। এবং তারপর, অ্যারের প্রতিটি উপাদানের জন্য, আমরা শেষ থেকে একটি উপাদান সরিয়ে অন্য একটি উপাদান যোগ করব। প্রতিটি স্লাইড করা উইন্ডোর জন্য আমরা প্রথম ঋণাত্মক সংখ্যা খুঁজে বের করব এবং মুদ্রণ করব। নেতিবাচক সংখ্যা খুঁজে বের করার জন্য আমরা পরীক্ষা করব যে অপসারিত নম্বরটি উইন্ডোর প্রথম ঋণাত্মক সংখ্যা কিনা, যদি হ্যাঁ আমরা প্রথম ঋণাত্মক সংখ্যার জন্য পরবর্তী উপাদানগুলি পরীক্ষা করব অন্যথায় না৷
উদাহরণ
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম
#include <bits/stdc++.h>
using namespace std;
void findFirstNegIntWindowK(int arr[], int n, int k){
deque<int> windowKsize;
int i = 0;
for (; i < k; i++)
if (arr[i] < 0)
windowKsize.push_back(i);
for (; i < n; i++){
if (!windowKsize.empty())
cout<<arr[windowKsize.front()]<<"\t";
else
cout<<"0\t";
while ( (!windowKsize.empty()) && windowKsize.front() < (i - k + 1))
windowKsize.pop_front();
if (arr[i] < 0)
windowKsize.push_back(i);
}
if (!windowKsize.empty())
cout<<arr[windowKsize.front()]<<" \t";
else
cout<<"0\t";
}
int main(){
int arr[] = {-2, 2, -1, 4, 3, -6};
int n = sizeof(arr)/sizeof(arr[0]);
int k = 2;
cout<<"First negative integer in each with of size "<<k<<" is \n";
findFirstNegIntWindowK(arr, n, k);
return 0;
} আউটপুট
First negative integer in each with of size 2 is -2 -1 -1 0 -6
