ধরুন একটি ইন্টিজার অ্যারে arr এবং দুটি ইন্টিজার k ও threshold দেওয়া আছে। সাইজ k এবং গড় threshold বা তার বেশি হয় এমন সাব-অ্যারে কতটি আছে তা বের করতে হবে। ইনপুট: [2,2,2,2,5,5,5,8], k = 3, threshold = 4 হলে আউটপুট ৩। কারণ সাবঅ্যারে [2,5,5], [5,5,5], [5,5,8]-এর গড় যথাক্রমে ৪, ৫, ৬।
সমাধানের ধাপগুলো:
sum := 0, div := k, n := অ্যারে এলিমেন্ট সংখ্যা
sum := arr-এর প্রথম k এলিমেন্টের যোগফল
ret := 0
i := 0 এবং j = k থেকে n – 1 পর্যন্ত, i ও j দুইটাই ১ বাড়াতে
যদি sum / div >= threshold হয়, তবে ret ১ বাড়ান
sum -= arr[i]
sum += arr[j]
শেষে যদি sum / div >= threshold হয়, তবে ret ১ বাড়ান
ret রিটার্ন করুন।
উদাহরণ (C++)
নিচের ইমপ্লিমেন্টেশন দেখুন ভালো বুঝতে −
#include <bits/stdc++.h> using namespace std; class Solution { public: int numOfSubarrays(vector<int>& arr, int k, int threshold) { double sum = 0; double div = k; int n = arr.size(); for(int i = 0; i < k; i++){ sum += arr[i]; } int ret = 0; for(int i = 0, j = k; j < n; i ++, j++){ if(sum / div >= threshold ){ ret++; } sum -= arr[i]; sum += arr[j]; } if(sum / div >= threshold ){ ret++; } return ret; } }; main(){ vector<int> v = {2,2,2,2,5,5,5,8}; Solution ob; cout << (ob.numOfSubarrays(v, 3, 4)); }
ইনপুট
[2,2,2,2,5,5,5,8] 3 4
আউটপুট
3
