Trong bài viết này, chúng tôi sẽ giải thích mọi thứ về việc giải quyết số mảng con có tổng dạng k ^ m, m> =0 trong C ++. Cho một mảng arr [] và một số nguyên K, chúng ta cần tìm số lượng các mảng con có tổng ở dạng K ^ m trong đó m lớn hơn bằng 0, hoặc chúng ta có thể nói chúng ta cần tìm số lượng các mảng con có tổng bằng một số lũy thừa không âm của 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 Có hai cách tiếp cận chủ yếu được nghĩ đến -
Lực lượng vũ phu
Trong cách tiếp cận này, chúng ta sẽ đi qua tất cả các mảng con và kiểm tra xem chúng có phải là một lũy thừa tích phân dương nào đó của K hay không; nếu có, thì chúng tôi tăng số lượng.
Ví dụ
#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";
} Đầu ra
8
Tuy nhiên, cách tiếp cận này không tốt lắm vì độ phức tạp về thời gian của chương trình này là O (N * N * log (K)), trong đó N là kích thước mảng của chúng ta và K là số nguyên do người dùng cung cấp.
Độ phức tạp này không tốt vì độ phức tạp này có thể được sử dụng cho các ràng buộc cao hơn vì sẽ mất quá nhiều thời gian để xử lý nếu các ràng buộc lớn, vì vậy chúng tôi sẽ thử một cách tiếp cận khác để có thể sử dụng chương trình cho các ràng buộc cao hơn.
Phương pháp tiếp cận hiệu quả
Trong cách tiếp cận này, chúng tôi sẽ sử dụng tổng tiền tố và bản đồ để giảm bớt quá trình xử lý sẽ giảm đáng kể độ phức tạp về thời gian của chúng tôi.
Ví dụ
#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;
} Đầu ra
8
Kết luận
Chúng tôi giải một bài toán để tìm Số lượng mảng con có tổng ở dạng k ^ m trong đó m> =0 trong O (nlog (k) log (n)) phức tạp về thời gian. Chúng tôi cũng đã học chương trình C ++ cho vấn đề này và cách tiếp cận hoàn chỉnh (Bình thường và hiệu quả) mà chúng tôi đã giải quyết vấn đề này. Chúng ta có thể viết cùng một chương trình bằng các ngôn ngữ khác như C, java, python và các ngôn ngữ khác. Hy vọng bạn thấy bài viết này hữu ích.