C++로 작성되어 합계가 k^m인 하위 배열의 수를 찾습니다. 여기서 m >= 0

이 글에서는 C++에서 합이 k^m, m >= 0인 하위 배열의 개수를 찾는 방법에 대해 모두 설명하겠습니다. 배열 arr[]과 정수 K가 주어지면, 합이 K^m 형식인 하위 배열의 수를 찾아야 하며, 여기서 m은 0보다 크거나 같습니다. 또는 다음을 사용하여 하위 배열의 수를 찾아야 한다고 말할 수 있습니다. K^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인지 아닌지 확인한 다음 개수를 증가시킵니다.

Example

#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

그러나 이 프로그램의 시간 복잡도는 O(N*N*log(K)), 이므로 이 접근 방식은 그리 좋지 않습니다. 여기서 N은 배열의 크기이고, K는 배열의 크기입니다. 사용자가 제공한 정수입니다.

이 복잡성은 더 높은 제약 조건에 사용될 수 있기 때문에 좋지 않습니다. 제약 조건이 크면 처리하는 데 너무 많은 시간이 걸리기 때문에 프로그램을 사용하여 더 높은 제약 조건을 달성할 수 있도록 다른 접근 방식을 시도할 것입니다.

효율적인 방법

이 방법에서는 접두사 합과 매핑을 사용하여 처리량을 줄여 시간 복잡도를 크게 줄입니다.

Example

#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

결론

합계가 k^m(여기서 m >= 0) 형식이고 시간 복잡도가 O(nlog(k)log(인 하위 배열의 수를 찾는 문제를 해결했습니다. n)) 시간 복잡도. 우리는 또한 이 문제를 해결하기 위한 C++ 프로그램과 이 문제를 해결하는 완전한 방법(정상적이고 효율적인)을 배웠습니다. C, Java, Python 및 기타 언어와 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다. 이 기사가 도움이 되기를 바랍니다.

위 내용은 C++로 작성되어 합계가 k^m인 하위 배열의 수를 찾습니다. 여기서 m >= 0의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!