Ditulis dalam C++, cari bilangan subarray yang jumlahnya ialah k^m, dengan m >= 0

Dalam artikel ini, kami akan menerangkan segala-galanya tentang mencari bilangan subarray yang jumlahnya ialah k^m, m >= 0 dalam C++. Memandangkan tatasusunan arr[] dan integer K, kita perlu mencari bilangan subarray dengan jumlah dalam bentuk K^m di mana m lebih besar daripada atau sama dengan 0, atau kita boleh katakan kita perlu mencari bilangan subarray dengan hasil tambah bentuk K^m Jumlah kuantiti adalah sama dengan beberapa kuasa bukan negatif 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

Terdapat dua kaedah -

Brute force

Dalam kaedah ini kita akan menggelungkan semua sub-tatasusunan dan memeriksa sama ada ia adalah K atau tidak, jika ya maka kita menambah kiraan.

Contoh

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

Output

8

Walau bagaimanapun, kaedah ini tidak begitu baik kerana kerumitan masa program ini ialah O(N*N*log(K)), , di mana N ialah saiz tatasusunan, K ialah saiz tatasusunan. Integer yang diberikan oleh pengguna.

Kerumitan ini tidak bagus kerana kerumitan ini boleh digunakan untuk kekangan yang lebih tinggi kerana jika kekangannya besar ia mengambil masa terlalu lama untuk diproses jadi kami akan cuba pendekatan lain supaya kami boleh menggunakan program untuk mencapai kekangan yang lebih tinggi.

Kaedah yang cekap

Dalam kaedah ini, kami akan menggunakan jumlah awalan dan pemetaan untuk mengurangkan pemprosesan, sekali gus mengurangkan kerumitan masa. < /p>

Contoh

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

Output

8

Kesimpulan

Kami menyelesaikan masalah untuk mencari bilangan subarray yang jumlahnya adalah k^m, dengan m >= 0, dengan kerumitan masa O(nlog(k)log(n)) Kerumitan masa. Kami juga mempelajari program C++ untuk menyelesaikan masalah ini dan cara lengkap untuk menyelesaikan masalah ini (biasa dan cekap). Kita boleh menulis program yang sama dalam bahasa lain seperti C, java, python dan bahasa lain. Semoga artikel ini bermanfaat kepada anda.

Atas ialah kandungan terperinci Ditulis dalam C++, cari bilangan subarray yang jumlahnya ialah k^m, dengan m >= 0. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!