এই সমস্যাতে, আমাদের একটি অ্যারে arr[] দেওয়া আছে যাতে N সংখ্যক ইন্টিজার মান আছে এবং একটি উইন্ডোর সাইজ K। আমাদের কাজ হল প্রতিটি উইন্ডোতে প্রথম নেগেটিভ ইন্টিজার বের করার প্রোগ্রাম তৈরি করা। যদি নেগেটিভ সংখ্যা থাকে তবে প্রিন্ট করব, নাও থাকলে ০ প্রিন্ট করব।
উদাহরণ দেখি:
ইনপুট: arr[] = {-2, 2, -1, 4, 3, -6}, k = 2 আউটপুট: -2, -1, -1, 0, -6
ব্যাখ্যা -
উইন্ডো সাইজ k = 2, {-2, 2}, প্রথম নেগেটিভ -2 {2, -1}, প্রথম নেগেটিভ -1 {-1, 4}, প্রথম নেগেটিভ -1 {4, 3}, প্রথম নেগেটিভ ০ (নেগেটিভ নেই) {3, -6}, প্রথম নেগেটিভ -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
আরেকটি দক্ষ পদ্ধতি হল স্লাইডিং উইন্ডো কনসেপ্ট ব্যবহার করা। এর জন্য একটি ডিকিউ (dequeue) (ডবল-এন্ডেড কিউ) 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
