Écrit en C++, trouvez le nombre de sous-tableaux dont la somme est k^m, où m >= 0

Dans cet article, nous expliquerons tout sur la recherche du nombre de sous-tableaux dont la somme est k^m, m >= 0 en C++. Étant donné un tableau arr[] et un entier K, nous devons trouver le nombre de sous-tableaux avec des sommes de la forme K^m où m est supérieur ou égal à 0, ou nous pouvons dire que nous devons trouver le nombre de sous-tableaux avec sommes de la forme K^m La somme des quantités est égale à une puissance non négative de 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

Il existe principalement deux méthodes -

Force brute

Dans cette méthode, nous allons parcourir tous les sous-tableaux et vérifier s'ils sont K ou non, puis nous incrémentons le nombre.

Exemple

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

Sortie

8

Cependant, cette approche n'est pas très bonne car la complexité temporelle de ce programme est O(N*N*log(K)), , où N est la taille du tableau, K est la taille du tableau. Un entier donné par l'utilisateur.

Cette complexité n'est pas bonne car cette complexité peut être utilisée pour des contraintes plus élevées car si les contraintes sont grandes, le traitement prend trop de temps, nous allons donc essayer une autre approche afin de pouvoir utiliser le programme pour atteindre des contraintes plus élevées.

Méthode efficace

Dans cette méthode, nous utiliserons la somme de préfixes et le mappage pour réduire le traitement, réduisant ainsi considérablement la complexité temporelle.

Exemple

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

Sortie

8

Conclusion

Nous avons résolu un problème pour trouver le nombre de sous-tableaux dont la somme est de la forme k^m, où m >= 0, avec une complexité temporelle O(nlog(k)log( n)) Complexité temporelle. Nous avons également appris un programme C++ pour résoudre ce problème et une manière complète de résoudre ce problème (normale et efficace). Nous pouvons écrire le même programme dans d'autres langages tels que C, Java, Python et d'autres langages. J'espère que cet article vous sera utile.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!