C++ หาจำนวน Subarray ที่มีผลรวมเป็นคี่ (Odd Sum)

Subarrays คือส่วนที่ติดต่อกันของอาร์เรย์ เช่น เราพิจารณาอาร์เรย์ [5, 6, 7, 8] จะมี Subarray ที่ไม่ว่าง 10 ชุด เช่น (5), (6), (7), (8), (5, 6), (6,7), (7,8), (5,6,7), (6,7,8) และ (5,6,7,8)

ในคู่มือนี้ เราจะอธิบายข้อมูลทุกอย่างที่เป็นไปได้เพื่อหาจำนวน Subarray ที่มีผลรวมเป็นคี่ใน C++ สำหรับการหาจำนวน Subarray ที่มีผลรวมเป็นคี่ เราสามารถใช้วิธีต่างๆ ได้ นี่คือตัวอย่างง่ายๆ สำหรับมัน

Input : array = {9,8,7,6,5} Output : 9 Explanation : ผลรวม Subarray - {9} = 9 {7} = 7 {5} = 5 {9,8} = 17 {8,7} = 15 {7,6} = 13 {6,5} = 11 {8,7,6} = 21 {9,8,7,6,5} = 35

วิธี Brute Force

ด้วยวิธีนี้ เราสามารถตรวจสอบได้อย่างง่ายว่าผลรวมของสมาชิกในทุก Subarray เป็นคู่หรือคี่ ถ้าเป็นคู่เราจะตัดทิ้งและนับ Subarray ที่ผลรวมเป็นคี่ ไม่ใช่วิธีที่มีประสิทธิภาพ เพราะความซับซ้อนของโค้ดนี้คือ O(n²)

ตัวอย่าง

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

int main(){ 
    int n=5, temp = 0; 
    int a[n-1] = { 9,8,7,6,5 }; 
    int cnt = 0; 
    for(int i = 0; i < n; i++){ 
        temp = 0; 
        for(int j = i; j < n; j++){ 
            temp = temp + a[j]; 
            if( temp % 2 == 1 ) cnt++; 
        } 
    } 
    cout << "Number of subarrays with odd sum : " << cnt << "\n"; 
    return 0; 
}

ผลลัพธ์

Number of subarrays with odd sum : 9

คำอธิบายโค้ด

ใช้ Nested Loops ในโค้ดนี้ ลูปนอกใช้เพิ่มค่า i ซึ่งชี้ที่แต่ละค่าของอาร์เรย์จากต้นทาง ลูปในใช้หา Subarray เริ่มจากตำแหน่ง "i" ที่มีผลรวมเป็นคี่

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

ในวิธีนี้ เราประมวลผลทุกสมาชิกจากตำแหน่ง 0 ในอาร์เรย์ ถ้าสมาชิกปัจจุบันเป็นคี่ เพิ่มตัวนับคี่ และเพิ่มตัวนับคู่สำหรับทุกเลขคู่ ถ้าเราพบเลขคี่ ให้สลับค่าของคู่และคี่ เพราะการเพิ่มเลขคี่เข้า Subarray จะเปลี่ยน Parity (ความเป็นคู่/คี่) และสุดท้ายเพิ่มตัวนับเข้า Result ความซับซ้อนของโค้ดนี้คือ O(n) เนื่องจากเราประมวลผลทุกสมาชิก

ตัวอย่าง

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

int main(){ 
    int odd = 0, even = 0, result = 0, n=5, i, temp; 
    int arr[n-1] = { 9,8,7,6,5 }; 
    for (i = 0; i < n; i++) { 
        if (arr[i] % 2 == 0) { 
            even++; 
        } else { 
            temp = even; 
            even = odd; 
            odd = temp + 1; 
        } 
        result += odd; 
    } 
    cout << "Number of subarrays with odd sum : " << result; 
}

ผลลัพธ์

Number of subarrays with odd sum : 9

คำอธิบายโค้ด

ในโค้ดนี้ เราตรวจสอบทุกสมาชิกว่าคู่หรือคี่ และเพิ่มตัวนับคู่สำหรับเลขคู่ และตัวนับคี่สำหรับเลขคี่ นอกจากนี้ เราก็สลับค่าตัวนับคี่-คู่ถ้าพบเลขคี่ มิฉะนั้นจะเปลี่ยน Parity ของ Subarray แล้วบวกค่าตัวนับคี่เข้า Result หลังการวนลูปทุกครั้ง

สรุป

ในบทความนี้ เราอธิบายวิธีหาจำนวน Subarray ที่ผลรวมเป็นคี่ จากวิธี Brute Force ที่สร้างทุก Subarray และนับที่ผลรวมเป็นคี่ ความซับซ้อน O(n²) วิธีมีประสิทธิภาพคือไปผ่านแต่ละสมาชิกของอาร์เรย์ และเพิ่มตัวนับคี่/คู่ กับทุกเลขคี่/คู่ที่พบ และสลับตัวนับถ้าพบเลขคี่ ความซับซ้อน O(n) หวังว่าบทความนี้จะช่วยให้เข้าใจปัญหาและวิธีแก้