আমাদেরকে পূর্ণসংখ্যা এবং একটি পরিবর্তনশীল X সমন্বিত একটি অ্যারে অ্যারে দেওয়া হয়েছে। লক্ষ্য হল অ্যার[]-এর সমস্ত সাব্যারে গণনা করা যাতে প্রতিটি সাব্যারেতে কেবলমাত্র X-এর কম বা সমান উপাদান থাকে। উদাহরণস্বরূপ যদি অ্যারে হয় [1, 2,3] এবং X=2 তারপর সাবয়ারে হবে [1], [2] এবং [1,2]
আসুন উদাহরণ দিয়ে বুঝতে পারি।
ইনপুট − arr[] ={ 4,3,2,1,6}; X=3
আউটপুট − সাব-অ্যারেগুলির সংখ্যা যেখানে X এর থেকে কম বা সমান উপাদান রয়েছে −6
ব্যাখ্যা − সুবারায় −
হবে[3], [2], [1], [3,2], [2,1], [3,2,1]
ইনপুট − arr[] ={ 3,6,2,7,1,8,5}; X=5
আউটপুট − সাব-অ্যারেগুলির সংখ্যা যেখানে X এর থেকে কম বা সমান উপাদান রয়েছে −4
ব্যাখ্যা − সুবারায় −
হবে[3], [2], [1], [5]
নিচের প্রোগ্রামে ব্যবহৃত পদ্ধতিটি নিম্নরূপ
আমরা একটি বাইনারি অ্যারে তৈরি করছি temp_arr[] মূল অ্যারে অ্যারের মতো একই আকারের। এই বাইনারি অ্যারেতে 1 থাকবে যদি সংশ্লিষ্ট arr[i] X-এর কম বা সমান হয়, অন্যথায় 0। এখন temp_arr[] ট্র্যাভার্স করুন এবং ক্রমাগত 1 এর জন্য পরীক্ষা করুন (এলারে X-এর থেকে কম উপাদান)। এই ধরনের প্রতিটি সাবয়ারের দৈর্ঘ্য তাপমাত্রায় সংরক্ষণ করুন। দৈর্ঘ্য তাপমাত্রা একটি অ্যারের জন্য. মোট সাব্যারে হবে temp*(temp+1)/2। এটি মোট গণনায় যোগ করুন এবং temp_arr[] শেষ না হওয়া পর্যন্ত চালিয়ে যান।
-
অ্যারে arr[] এবং পরিবর্তনশীল X.
নিন -
ফাংশন sub_X(int arr[], int size, int x) অ্যারে এবং x নেয় এবং শুধুমাত্র x এর থেকে কম বা সমান উপাদান সহ সাবয়ারের গণনা প্রদান করে।
-
গণনা হিসাবে অস্থায়ী পরিবর্তনশীল টেম্প এবং এই জাতীয় সাবয়ারের চূড়ান্ত মোট নিন।
-
arr[] এর মতো দৈর্ঘ্যের একটি বাইনারি অ্যারে temp_arr[] নিন।
-
আমরা i=0 থেকে i
-
প্রতিটি উপাদানের জন্য arr[i]<=x, temp_arr[i]=1 অন্য 0 সেট করুন।
-
ট্রাভার্স temp_arr[] লুপের জন্য ব্যবহার করে।
-
যদি কোন উপাদান temp_arr[i] ==1. তারপর বর্তমান সূচক i থেকে temp_arr[temp_2] ( temp_2=i+1; temp_2
-
সমস্ত 1 এর সাথে সাবয়ারের গণনা হবে temp=temp_2-i.
-
এই সাবঅ্যারেতে সমস্ত 1 আছে যার অর্থ হল arr[i] এর সমস্ত উপাদান হল <=x। মোট সাবঅ্যারে হবে temp_3=temp*(temp+1)/2।
-
উভয় ট্রাভার্সালের শেষে, গণনায় অ্যারের মধ্যে থাকা সমস্ত সাবয়ারের গণনার মোট সংখ্যা থাকবে যার সংখ্যা x এর চেয়ে কম বা সমান।
উদাহরণ
#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