এই আর্টিকেলে আমরা মিনিমাম (minimum) এবং ম্যাক্সিমাম (maximum) এলিমেন্ট একই হলে সাবঅ্যারে সংখ্যা বের করার সমস্যা C++ দিয়ে সমাধান করব। উদাহরণ −
ইনপুট: array = { 2, 3, 6, 6, 2, 4, 4, 4 } আউটপুট: 12 ব্যাখ্যা: {2}, {3}, {6}, {6}, {2}, {4}, {4}, {4}, {6,6}, {4,4}, {4,4}, {4,4,4} - এই সাবঅ্যারেগুলোর মিন ও ম্যাক্স একই।
ইনপুট: array = { 3,3,1,5,1,2,2 } আউটপুট: 9 ব্যাখ্যা: {3}, {3}, {1}, {5}, {1}, {2}, {2}, {3,3}, {2,2} - মিন ও ম্যাক্স একই।
উদাহরণগুলো দেখলে বলা যায়, কমপক্ষে অ্যারে সাইজ (n) সংখ্যক সাবঅ্যারে বানাবে যাদের মিন ও ম্যাক্স একই। কম্পার্টিভ (consecutive) একই সংখ্যা থাকলে সাবঅ্যারে সংখ্যা বাড়ে।
তাই আমরা একটি পদ্ধতি প্রয়োগ করতে পারি: প্রতিটি এলিমেন্ট প্রসেস করে চেক করব এর কমপার্টিভ নাকি (consecutive) সংখ্যাগুলো একই কিনা। একই হলে কাউন্ট বাড়াব, ভিন্ন হলে ইননার লুপ ব্রেক (break) করব।
রেজাল্ট ভেরিয়েবল (result variable) ইননার লুপ খতম বা ব্রেক হলে বড়াবে এবং শেষে রেজাল্ট ভেরিয়েবল থেকে ফলাফল দেখাবে।
#include <bits/stdc++.h> using namespace std; int main(){ int a[ ] = { 2, 4, 5, 3, 3, 3 }; int n = sizeof(a) / sizeof(a[0]); int result = n, count = 0; for (int i = 0; i < n; i++) { for (int j = i+1; j < n; j++) { if(a[i] == a[j]) count++; else break; } result += count; count = 0; } cout << "Number of subarrays having minimum and maximum elements same:" << result; return 0; }
Number of subarrays having minimum and maximum elements same: 9 Time complexity = O(n²).
এই কোডে, n ভেরিয়েবলে অ্যারে সাইজ, result = n (কারণ কমপক্ষে n সাবঅ্যারে বানবে), count = একই সংখ্যা কাউন্ট রাখতে। বাহিরের লুপ প্রতিটি এলিমেন্ট প্রসেস করে। ভেতরের লুপ করেন্ট ইনডেক্সের পর কতগুলো কমপার্টিভ একই সংখ্যা আছে চেক করে count বাড়ায়। ইননার লুপ শেষে result-এ count যোগ করা হয়। শেষে result-এ থাকা আউটপুট দেখানো হয়।
এই পদ্ধতিতে, আমরা প্রতিটি এলিমেন্ট প্রসেস করি এবং প্রতিটি এলিমেন্টের জন্য কতগুলো কমপার্টিভ একই সংখ্যা আছে সেটি খুঁজি। প্রতিটি একই সংখ্যা পাওয়ায় count বাড়াই, ভিন্ন সংখ্যা পাওয়া গেলে count দিয়ে কতগুলো সাবঅ্যারে বানানো যাবে সেটি সূত্র n = n*(n+1)/2 দিয়ে বের করে result-এ যোগ করি।
#include <bits/stdc++.h> using namespace std; int main(){ int a[] = { 2, 4, 5, 3, 3, 3 }; int n = sizeof(a) / sizeof(a[0]); int result = 0; int count = 1, temp = a[0]; for (int i = 1; i < n; i++) { if (temp == a[i]){ count++; } else{ temp = a[i]; result = result + (count * (count + 1) / 2); count = 1; } } result = result + (count * (count + 1) / 2); cout << "Number of subarrays having minimum and maximum elements same:" << result; return 0; }
Number of subarrays having minimum and maximum elements same: 9 Time complexity : O(n)
এই কোডে, ০-তম ইনডেক্স temp-এ রাখা হয়েছে এবং লুপ ১-ই ইনডেক্স থেকে শুরু। temp করেন্ট ইনডেক্সের এলিমেন্টের সমান কিনা চেক করে একই হলে count বাড়ানো হয়েছে। temp != a[i] হলে, count দিয়ে সাবঅ্যারে কম্বিনেশন (count*(count+1)/2) বের করে result-এ যোগ করা হয়েছে। temp আপডেট করে count রিসেট (reset) করা হয়েছে। শেষে result-এ থাকা উত্তর দেখানো হয়েছে।
এই আর্টিকেলে আমরা মিনিমাম ও ম্যাক্সিমাম একই সাবঅ্যারে সংখ্যা বের করার সমস্যা সমাধান করেছি। আমরা এই সমস্যার C++ প্রোগ্রাম ও সম্পূর্ণ পদ্ধতি (সহজ ও দক্ষ) দেখেছি। একই প্রোগ্রাম C, Java, Python ইত্যাদি ভাষায়ও লিখা যায়। আশা করি আপনি এই আর্টিকেলটি সহায়ক পাবেন।
