ในบทความนี้ เราจะอธิบายทุกอย่างเกี่ยวกับการแก้จำนวนอาร์เรย์ย่อยที่มีผลรวมของรูปแบบ k^m, m>=0 ใน C++ จากอาร์เรย์ arr[] และจำนวนเต็ม K เราจำเป็นต้องค้นหาจำนวนอาร์เรย์ย่อยที่มีผลรวมในรูปแบบของ K^m โดยที่ 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 หรือไม่ ถ้าใช่ เราก็เพิ่มจำนวนขึ้น
ตัวอย่าง
#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
บทสรุป
เราแก้ปัญหาเพื่อหาจำนวนอาร์เรย์ย่อยที่มีผลรวมในรูปแบบของ k^m โดยที่ m>=0 ใน O(nlog(k)log(n)) ความซับซ้อนของเวลา นอกจากนี้เรายังได้เรียนรู้โปรแกรม C ++ สำหรับปัญหานี้และแนวทางที่สมบูรณ์ ( Normal และ มีประสิทธิภาพ ) โดยที่เราแก้ไขปัญหานี้ เราสามารถเขียนโปรแกรมเดียวกันในภาษาอื่นๆ เช่น C, java, python และภาษาอื่นๆ หวังว่าบทความนี้จะเป็นประโยชน์
