C++ หาจำนวน Subarray ที่มีผลรวมเป็นรูป k^m (m ≥ 0)

ในบทความนี้ เราจะอธิบายทุกอย่างเกี่ยวกับการแก้ปัญหาจำนวน Subarray ที่มีผลรวมเป็นรูป k^m, m ≥ 0 ใน C++ กำหนดอาร์เรย์ arr[] และจำนวนเต็ม K เราต้องหาจำนวน Subarray ที่มีผลรวมในรูป K^m โดยที่ m มากกว่าหรือเท่ากับศูนย์ หรือพูดง่ายๆ คือหาจำนวน Subarray ที่มีผลรวมเท่ากับกำลังของ K ที่ไม่เป็นลบ

Input: arr[] = { 2, 2, 2, 2 } K = 2 Output: 8 Sub-arrays ที่มีดัชนีดังต่อไปนี้ถูกต้อง: [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

มีสองวิธีหลักที่นึกออกมา

Brute Force

ในวิธีนี้ เราจะไปผ่านทุก Subarray และตรวจสอบว่ามันเป็นกำลังบวกของ K หรือไม่ ถ้าใช่ ให้เพิ่ม Count

ตัวอย่าง

#include <bits/stdc++.h> 
#define MAX 1000000 
using namespace std; 

int main(){ 
    int arr[] = {2, 2, 2, 2}; 
    int k = 2; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    int answer = 0; 
    for(int i = 0; i < n; i++){ 
        int sum = 0; 
        for(int j = i; j < n; j++){ 
            sum += arr[j]; 
            int b = 1; 
            while(b < MAX && sum > b) 
                b *= k; 
            if(b == sum) answer++; 
        } 
    } 
    cout << answer << "\n"; 
}

ผลลัพธ์

8

อย่างไรก็ตาม วิธีนี้ไม่ค่อยดี เพราะ Time Complexity คือ O(N*N*log(K)) โดย N คือขนาดอาร์เรย์ และ K คือจำนวนเต็มที่ผู้ใช้ให้ ความซับซ้อนนี้ไม่ดี เพราะถ้าข้อจำกัดใหญ่ จะใช้เวลาประมวลผลมากเกินไป เราจะลองอีกวิธีเพื่อให้ใช้ได้กับข้อจำกัดที่สูงกว่า

วิธีมีประสิทธิภาพ (Efficient Approach)

ในวิธีนี้ เราจะใช้ Prefix Sum และ Map เพื่อลดการประมวลผล ซึ่งจะลด Time Complexity อย่างมาก

ตัวอย่าง

#include <bits/stdc++.h> 
#define ll long long 
#define MAX 1000000 
using namespace std; 

int main(){ 
    int arr[] = {2, 2, 2, 2}; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    int k = 2; 
    ll prefix_sum[MAX]; 
    prefix_sum[0] = 0; 
    partial_sum(arr, arr + n, prefix_sum + 1); 
    ll sum; 
    if (k == 1){ 
        sum = 0; 
        map<ll, int> m; 
        for (int i = n; i >= 0; i--){ 
            if (m.find(prefix_sum[i] + 1) != m.end()) 
                sum += m[prefix_sum[i] + 1]; 
            m[prefix_sum[i]]++; 
        } 
        cout << sum << "\n"; 
    } else if (k == -1){ 
        sum = 0; 
        map<ll, int> m; 
        for (int i = n; i >= 0; i--){ 
            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]; 
            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){ 
                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

สรุป

เราแก้ปัญหาการหา Number of subarrays having sum in the form of k^m where m ≥ 0 ใน Time Complexity O(n log(k) log(n)) เรายังได้เรียนรู้โปรแกรม C++ สำหรับปัญหานี้ และวิธีแก้ปัญหา (ทั่วไปและมีประสิทธิภาพ) ซึ่งเราสามารถเขียนโปรแกรมเดียวกันในภาษาอื่น เช่น C, Java, Python ได้ หวังว่าจะเป็นประโยชน์