इस लेख में, हम C++ में k^m रूप में योग वाले सबएरे की संख्या को हल करने के बारे में सब कुछ समझाएंगे, जहां m >= 0। दी गई एक सरणी arr[] और एक पूर्णांक K, हमें k^m रूप में योग वाले सबएरे की संख्या ढूंढनी है जहां m शून्य से बड़ा या बराबर है, या हम कह सकते हैं कि हमें K की किसी गैर-ऋणात्मक घात के बराबर योग वाले सबएरे की संख्या ढूंढनी है।
इनपुट: 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 की कोई धनात्मक पूर्णांक घात हैं या नहीं; यदि हां, तो हम काउंट बढ़ाते हैं।
उदाहरण
#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 मैक्स 10^6 होना चाहिए b *= k; if(b == sum) // यदि b == sum तो काउंट बढ़ाएं 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}; // दी गई सरणी 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){ // हम 1 के लिए अलग से चेक करने जा रहे हैं sum = 0; map<ll, int> m; for (int i = n; i >= 0; i--){ // यदि m[a+b] = c, तो वर्तमान योग में c जोड़ें। 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){ // हम -1 के लिए अलग से चेक करने जा रहे हैं sum = 0; map<ll, int> m; for (int i = n; i >= 0; i--){ // यदि m[a+b] = c, तो वर्तमान योग में c जोड़ें। 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 से अधिक चेक नहीं करने जा रहे हैं // यदि m[a+b] = c, तो वर्तमान योग में c जोड़ें। 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
निष्कर्ष
हम O(nlog(k)log(n)) समय जटिलता में k^m रूप में योग वाले सबएरे की संख्या ढूंढने की समस्या को हल करते हैं जहां m >= 0। हमने इस समस्या के लिए C++ प्रोग्राम और पूरा दृष्टिकोण (सामान्य और कुशल) भी सीखा जिससे हमने इस समस्या को हल किया। हम यही प्रोग्राम C, Java, Python, और अन्य भाषाओं में भी लिख सकते हैं। आशा है आपको यह लेख उपयोगी लगा होगा।