এই নিবন্ধে, আমরা C++ এ k^m, m>=0 ফর্মের যোগফল সহ সাবয়ারের সংখ্যা সমাধান করার বিষয়ে সবকিছু ব্যাখ্যা করব। একটি অ্যারে অ্যারে[] এবং একটি পূর্ণসংখ্যা K দেওয়া হলে, আমাদের K^m আকারে যোগফল যুক্ত সাবয়ারের সংখ্যা খুঁজে বের করতে হবে যেখানে m শূন্যের সমান, অথবা আমরা বলতে পারি যে আমাদের সাবয়ারের সংখ্যা খুঁজে বের করতে হবে K.
এর কিছু অ-ঋণাত্মক শক্তির সমানInput: arr[] = { 2, 2, 2, 2 } K = 2
Output: 8
Sub-arrays with below indexes are valid:
[1, 1], [2, 2], [3, 3], [4, 4], [1, 2],
[2, 3], [3, 4], [1, 4]
Input: arr[] = { 3, -6, -3, 12 } K = -3
Output: 3 এখানে প্রধানত দুটি পন্থা আছে যা মনে আসে −
ব্রুট ফোর্স
এই পদ্ধতিতে, আমরা সমস্ত সাবয়ারের মধ্য দিয়ে যাব এবং পরীক্ষা করব যে সেগুলি K-এর কিছু ধনাত্মক অবিচ্ছেদ্য শক্তি কি না; যদি হ্যাঁ, তাহলে আমরা গণনা বৃদ্ধি করি।
উদাহরণ
#include <bits/stdc++.h>
#define MAX 1000000
using namespace std;
int main(){
int arr[] = {2, 2, 2, 2}; // given array
int k = 2; // given integer
int n = sizeof(arr) / sizeof(arr[0]); // the size of our array
int answer = 0; // counter variable
for(int i = 0; i < n; i++){
int sum = 0;
for(int j = i; j < n; j++){ // this will loop will make all the subarrays
sum += arr[j];
int b = 1;
while(b < MAX && sum > b) // k^m Max should be 10^6
b *= k;
if(b == sum) // if b == sum then increment count
answer++;
}
}
cout << answer << "\n";
} আউটপুট
8
যাইহোক, এই পদ্ধতিটি খুব ভাল নয় কারণ এই প্রোগ্রামের সময় জটিলতা হল O(N*N*log(K)), যেখানে N হল আমাদের অ্যারের আকার এবং K হল ব্যবহারকারীর দেওয়া পূর্ণসংখ্যা।
এই জটিলতাটি ভাল নয় কারণ এই জটিলতাটি উচ্চ সীমাবদ্ধতার জন্য ব্যবহার করা যেতে পারে কারণ সীমাবদ্ধতাগুলি বড় হলে এটি প্রক্রিয়া করতে অনেক বেশি সময় লাগবে, তাই আমরা অন্য পদ্ধতির চেষ্টা করব যাতে আমরা উচ্চ সীমাবদ্ধতার জন্য প্রোগ্রামটি ব্যবহার করতে পারি।
দক্ষ পদ্ধতি
এই পদ্ধতিতে, আমরা আমাদের প্রক্রিয়াকরণ কমাতে একটি উপসর্গ যোগফল এবং মানচিত্র ব্যবহার করব যা আমাদের সময় জটিলতাকে ব্যাপকভাবে হ্রাস করবে।
উদাহরণ
#include <bits/stdc++.h>
#define ll long long
#define MAX 1000000
using namespace std;
int main(){
int arr[] = {2, 2, 2, 2}; // The given array
int n = sizeof(arr) / sizeof(arr[0]); // size of our array
int k = 2; // given integer
ll prefix_sum[MAX];
prefix_sum[0] = 0;
partial_sum(arr, arr + n, prefix_sum + 1); // making prefix sum array
ll sum;
if (k == 1){
// we are going to check separately for 1
sum = 0;
map<ll, int> m;
for (int i = n; i >= 0; i--){
// If m[a+b] = c, then add c to the current sum.
if (m.find(prefix_sum[i] + 1) != m.end())
sum += m[prefix_sum[i] + 1];
// Increase count of prefix sum.
m[prefix_sum[i]]++;
}
cout << sum << "\n";
}
else if (k == -1){
// we are going to check separately for -1
sum = 0;
map<ll, int> m;
for (int i = n; i >= 0; i--){
// If m[a+b] = c, then add c to the current sum.
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];
// Increase count of prefix sum.
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){ // we are not going to check for more than 10^6
// If m[a+b] = c, then add c to the current sum.
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 in O(nlog(k)log(n)) সময় জটিলতা। আমরা এই সমস্যার জন্য C++ প্রোগ্রাম এবং সম্পূর্ণ পদ্ধতি ( স্বাভাবিক এবং দক্ষ) শিখেছি যার মাধ্যমে আমরা এই সমস্যার সমাধান করেছি। আমরা অন্যান্য ভাষা যেমন সি, জাভা, পাইথন এবং অন্যান্য ভাষায় একই প্রোগ্রাম লিখতে পারি। আশা করি আপনি এই নিবন্ধটি সহায়ক বলে মনে করেন৷
