इस लेख में, हम 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++ प्रोग्राम और संपूर्ण दृष्टिकोण (सामान्य और कुशल) भी सीखा जिसके द्वारा हमने इस समस्या को हल किया। हम उसी प्रोग्राम को अन्य भाषाओं जैसे सी, जावा, पायथन और अन्य भाषाओं में लिख सकते हैं। आशा है कि आपको यह लेख मददगार लगा होगा।