Ermitteln Sie in C++ die Anzahl der Subarrays, deren Summe k^m ist, wobei m >= 0 ist

In diesem Artikel erklären wir alles über das Ermitteln der Anzahl von Subarrays, deren Summe k^m, m >= 0 in C++ ist. Bei einem gegebenen Array arr[] und einer ganzen Zahl K müssen wir die Anzahl der Subarrays mit Summen der Form K^m ermitteln, wobei m größer oder gleich 0 ist, oder wir können sagen, wir müssen die Anzahl der Subarrays mit ermitteln Summen der Form K^m Die Summe der Größen ist gleich einer nichtnegativen Potenz von 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

Es ​​gibt hauptsächlich zwei Methoden –

Brute Force

Bei dieser Methode durchlaufen wir alle Unterarrays und prüfen, ob sie K sind oder nicht. Wenn ja, erhöhen wir die Anzahl.

Beispiel

#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";
}

Ausgabe

8

Dieser Ansatz ist jedoch nicht sehr gut, da die zeitliche Komplexität dieses Programms O(N*N*log(K)), beträgt, wobei N die Größe des Arrays ist. K ist die Größe des Arrays. Eine vom Benutzer angegebene Ganzzahl.

Diese Komplexität ist nicht gut, da diese Komplexität für höhere Einschränkungen verwendet werden kann, da die Verarbeitung bei großen Einschränkungen zu viel Zeit in Anspruch nimmt. Daher werden wir einen anderen Ansatz ausprobieren, damit wir das Programm verwenden können, um höhere Einschränkungen zu erreichen.

Effiziente Methode

Bei dieser Methode verwenden wir Präfixsumme und Zuordnung, um die Verarbeitung zu reduzieren und dadurch die Zeitkomplexität erheblich zu reduzieren.

Beispiel

#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;
}

Ausgabe

8

Schlussfolgerung

Wir haben ein Problem gelöst, um die Anzahl der Subarrays zu ermitteln, deren Summe die Form k^m hat, wobei m >= 0, mit der Zeitkomplexität O(nlog(k)log( n)) Zeitkomplexität. Wir haben auch ein C++-Programm zur Lösung dieses Problems und einen vollständigen Weg zur Lösung dieses Problems (normal und effizient) gelernt. Wir können das gleiche Programm in anderen Sprachen wie C, Java, Python und anderen schreiben. Ich hoffe, dieser Artikel ist hilfreich für Sie.

Das obige ist der detaillierte Inhalt vonErmitteln Sie in C++ die Anzahl der Subarrays, deren Summe k^m ist, wobei m >= 0 ist. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!