এই আর্টিকেলে আমরা k^m রূপে (m ≥ 0) যোগফল 가진 সাবঅ্যারে সংখ্যা বের করার সমস্যা C++-এ ব্যাখ্যা করব। একটি অ্যারে arr[] এবং পূর্ণসংখ্যা K দেওয়া আছে। আমাদের বের করতে হবে কতগুলো সাবঅ্যারের যোগফল K^m রূপে আছে যেখানে m ≥ ০, অর্থাৎ K-এর কোনো নন-নেগেটিভ পাওয়ার (non-negative power) এর সমান।
ইনপুট: arr[] = { 2, 2, 2, 2 } K = 2 আউটপুট: 8 বৈধ সাব-অ্যারে (ইনডেক্স): [1,1], [2,2], [3,3], [4,4], [1,2], [2,3], [3,4], [1,4]
ইনপুট: arr[] = { 3, -6, -3, 12 } K = -3 আউটপুট: 3
মुख্যভাবে দুটি পদ্ধতি মনে পড়ে −
এই পদ্ধতিতে, সব সাবঅ্যারে চেক করব সেটি K-এর কোনো পজিটিভ ইন্টিজার পাওয়ার (positive integral power) কিনা; হ্যাঁ হলে কাউন্ট বাড়াব।
#include <bits/stdc++.h> #define MAX 1000000 using namespace std; int main(){ int arr[] = {2, 2, 2, 2}; // দেওয়া অ্যারে int k = 2; // দেওয়া ইন্টিজার int n = sizeof(arr) / sizeof(arr[0]); // অ্যারে সাইজ int answer = 0; // কাউন্টার for(int i = 0; i < n; i++){ int sum = 0; for(int j = i; j < n; j++){ // সব সাবঅ্যারে তৈরি sum += arr[j]; int b = 1; while(b < MAX && sum > b) // k^m MAX 10^6 b *= k; if(b == sum) answer++; // b == sum হলে কাউন্ট বাড়ানো } } cout << answer << "\n"; }
8
তবে এই পদ্ধতি ভালো নয় কারণ এর টাইম কমপ্লেক্সিটি O(N² log K), যেখানে N = অ্যারে সাইজ, K = দেওয়া ইন্টিজার। উচ্চ কনস্ট্রেইন্টের জন্য এটি অনেক সময় নেবে, তাই আরেকটি পদ্ধতি ব্যবহার করব।
এই পদ্ধতিতে, প্রিফিক্স সম (prefix sum) এবং ম্যাপ (map) ব্যবহার করে প্রসেসিং কমিয়ে টাইম কমপ্লেক্সিটি δραষ্টিক্যালি (drastically) কমিয়ে আনা যাবে।
#include <bits/stdc++.h> #define ll long long #define MAX 1000000 using namespace std; int main(){ int arr[] = {2, 2, 2, 2}; // দেওয়া অ্যারে int n = sizeof(arr) / sizeof(arr[0]); // অ্যারে সাইজ int k = 2; // দেওয়া ইন্টিজার ll prefix_sum[MAX]; prefix_sum[0] = 0; partial_sum(arr, arr + n, prefix_sum + 1); // প্রিফিক্স সম অ্যারে ll sum; if (k == 1){ // k=1 আলাদা চেক sum = 0; map<ll, int> m; for (int i = n; i >= 0; i--){ if (m.find(prefix_sum[i] + 1) != m.end()) sum += m[prefix_sum[i] + 1]; m[prefix_sum[i]]++; // প্রিফিক্স সম কাউন্ট বাড়ানো } cout << sum << "\n"; } else if (k == -1){ // k=-1 আলাদা চেক sum = 0; map<ll, int> m; for (int i = n; i >= 0; i--){ if (m.find(prefix_sum[i] + 1) != m.end()) sum += m[prefix_sum[i] + 1]; if (m.find(prefix_sum[i] - 1) != m.end()) sum += m[prefix_sum[i] - 1]; m[prefix_sum[i]]++; } cout << sum << "\n"; } else{ // সাধারণ কেস sum = 0; ll b; map<ll, int> m; for (int i = n; i >= 0; i--){ b = 1; while (b < MAX){ // 10^6 চেয়ে বেশি চেক করব না if (m.find(prefix_sum[i] + b) != m.end()) sum += m[prefix_sum[i] + b]; b *= k; } m[prefix_sum[i]]++; } cout << sum << "\n"; } return 0; }
8
আমরা k^m রূপে (m ≥ 0) যোগফল 가진 সাবঅ্যারে সংখ্যা বের করার সমস্যা O(n log k log n) টাইম কমপ্লেক্সিটিতে সমাধান করেছি। আমরা এই সমস্যার C++ প্রোগ্রাম ও সম্পূর্ণ পদ্ধতি (সহজ ও দক্ষ) দেখেছি। একই প্রোগ্রাম C, Java, Python ইত্যাদি ভাষায়ও লিখা যায়। আশা করি আপনি এই আর্টিকেলটি সহায়ক পাবেন।
