আমাদের একটি অ্যারে arr[] দেওয়া আছে যাতে পূর্ণসংখ্যা রয়েছে এবং একটি ভেরিয়েবল X। লক্ষ্য হলো arr[]-এর সব সাবঅ্যারে যাতে শুধু X-এর চেয়ে ছোট বা সমান উপাদান রয়েছে, তাদের সংখ্যা বের করা। উদাহরণস্বরূপ, অ্যারে [1,2,3] এবং X=2 হলে সাবঅ্যারে গুলো: [1], [2], [1,2]।
উদাহরণ দিয়ে বুঝি
ইনপুট − arr[] = { 4,3,2,1,6 }; X=3
আউটপুট − X-এর চেয়ে ছোট বা সমান উপাদানধর্মী সাবঅ্যারে সংখ্যা: ৬
ব্যাখ্যা − সাবঅ্যারে গুলো: [3], [2], [1], [3,2], [2,1], [3,2,1]
ইনপুট − arr[] = { 3,6,2,7,1,8,5 }; X=5
আউটপুট − X-এর চেয়ে ছোট বা সমান উপাদানধর্মী সাবঅ্যারে সংখ্যা: ৪
ব্যাখ্যা − সাবঅ্যারে গুলো: [3], [2], [1], [5]
প্রোগ্রামে ব্যবহৃত পদ্ধতি
আমরা মূল অ্যারে arr[]-এর সমান সাইজের একটি বাইনারি অ্যারে temp_arr[] তৈরি করব। এই বাইনারি অ্যারেতে arr[i] <= X হলে ১, অন্যথায় ০ থাকবে। এখন temp_arr[] ট্রাভার্স করে רציף ১ গুলো (যা মানে arr[]-এ X-এর চেয়ে ছোট উপাদান) খুঁজব। প্রতিটি এমন সাবঅ্যারের দৈর্ঘ্য temp-এ রাখব। দৈর্ঘ্য temp এর অ্যারের মোট সাবঅ্যারে হবে temp*(temp+1)/2। এটাকে মোট কাউন্টে যোগ করে শেষ পর্যন্ত চলব।
- অ্যারে
arr[]এবং ভেরিয়েবলXনিন। sub_X(int arr[], int size, int x)ফাংশন অ্যারে এবং x নিয়ে X-এর চেয়ে ছোট বা সমান উপাদানধর্মী সাবঅ্যারে কাউন্ট রিটার্ন করে।- অস্থায়ী ভেরিয়েবল
tempএবং ফাইনাল টোটালcountনিন। - মূল অ্যারের সমান দৈর্ঘ্যের বাইনারি অ্যারে
temp_arr[]নিন। i=0থেকেi<sizeপর্যন্ত লুপেarr[i]<=xহলেtemp_arr[i]=1, অন্যথায় ০।temp_arr[]ট্রাভার্স করুন।- যদি
temp_arr[i] == 1হয়, সাবলুপেtemp_2 = i+1থেকে শুরু করে যতক্ষণtemp_arr[temp_2] == 1ততক্ষণ চলুন। ০ পাওয়া গেলে ব্রেক করুন। - সাবঅ্যারের দৈর্ঘ্য
temp = temp_2 - i। - মোট সাবঅ্যারে
temp_3 = temp*(temp+1)/2। এটাকেcount-এ যোগ করুন। i = temp_2সেট করে পরবর্তী সেগমেন্টে যান।- শেষে
countরিটার্ন করুন।
উদাহরণ
#include <iostream>
using namespace std;
int sub_X(int arr[], int size, int x) {
int count = 0, temp = 0;
int temp_arr[size];
for (int i = 0; i < size; i++) {
if (arr[i] <= x) {
temp_arr[i] = 1;
} else {
temp_arr[i] = 0;
}
}
for (int i = 0; i < size; i++) {
if (temp_arr[i] == 1) {
int temp_2;
for (temp_2 = i + 1; temp_2 < size; temp_2++) {
if (temp_arr[temp_2] != 1) {
break;
}
}
temp = temp_2 - i;
int temp_3 = (temp) * (temp + 1) / 2;
count = count + temp_3;
i = temp_2;
}
}
return count;
}
int main() {
int arr[] = { 2, 6, 1, 10, 5, 3 };
int x = 4;
int size = sizeof(arr) / sizeof(arr[0]);
cout << "Count of sub-arrays which have elements less than or equal to X are: " << sub_X(arr, size, x);
return 0;
}
আউটপুট
Count of sub-arrays which have elements less than or equal to X are: 3
