이 기사에서 우리는 C++에서 k^m, m>=0 형식의 합을 갖는 부분배열의 수를 푸는 것에 대한 모든 것을 설명할 것입니다. 배열 arr[]와 정수 K가 주어지면 K^m 형식의 합계를 갖는 하위 배열의 수를 찾아야 하며 여기서 m은 0보다 크거나 다음을 갖는 하위 배열의 수를 찾아야 한다고 말할 수 있습니다. 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의 양의 적분 거듭제곱인지 확인합니다. 그렇다면 카운트를 증가시킵니다.
예시
#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";
} 출력
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}; // 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;
} 출력
8
결론
O(nlog(k)log(n))에서 m>=0인 k^m 형식의 합계를 갖는 하위 배열의 수를 찾는 문제를 풉니다. 시간 복잡도. 우리는 또한 이 문제에 대한 C++ 프로그램과 이 문제를 해결하는 완전한 접근 방식( Normal 및 Efficient)을 배웠습니다. C, Java, python 및 기타 언어와 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다. 이 기사가 도움이 되기를 바랍니다.