C++ หาจำนวน Subarray ที่มีเลขคี่ m ตัว (Number of Subarrays with m Odd Numbers)

ถ้าคุณเคยใช้ C++ คุณต้องรู้ว่า Subarrays คืออะไรและมีประโยชน์อย่างไร ตามที่เรารู้ว่าใน C++ เราสามารถแก้ปัญหาทางคณิตศาสตร์หลายอย่างได้ง่าย ในบทความนี้ เราจะอธิบายข้อมูลครบถ้วนเกี่ยวกับวิธีหา M odd numbers ด้วยความช่วยเหลือของ Subarrays ใน C++

ในปัญหานี้ เราต้องหาจำนวน Subarray ที่สร้างจากอาร์เรย์ที่กำหนดและจำนวนเต็ม m โดยที่แต่ละ Subarray ต้องมีเลขคี่ (Odd Numbers) อยู่ครบ m ตัว นี่คือตัวอย่างง่ายๆ สำหรับวิธีนี้

Input : array = { 6,3,5,8,9 }, m = 2 Output : 5 Explanation : Subarrays ที่มีเลขคี่ 2 ตัวคือ { 3,5 }, { 6,3,5 }, { 3,5,8 }, { 5,8,9 }, { 6,3,5,8 }, { 3,5,8,9 }
Input : array = { 1,6,3,2,5,4 }, m = 2 Output : 6 Explanation : Subarrays ที่มีเลขคี่ 2 ตัวคือ { 1,6,3 }, { 3,2,5 }, { 1,6,3,2 }, { 6,3,2,5 }, { 3,2,5,4 }, { 6,3,2,5,4 }

วิธีแรก (First Approach)

ในวิธีนี้ สร้าง Subarray ทั้งหมดที่เป็นไปได้จากอาร์เรย์ที่กำหนด และตรวจสอบแต่ละ Subarray ว่ามีเลขคี่ m ตัวพอดีหรือไม่ เป็นวิธี Generate และ Find แบบง่าย ความซับซ้อน O(n²)

ตัวอย่าง

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

int main (){ 
    int a[] = { 1, 6, 3, 2, 5, 4 }; 
    int n = 6, m = 2, count = 0; 
    for (int i = 0; i < n; i++){ 
        int odd = 0; 
        for (int j = i; j < n; j++) { 
            if (a[j] % 2) odd++; 
            if (odd == m) count++; 
        } 
    } 
    cout << "Number of subarrays with n numbers are: " << count; 
    return 0; 
}

ผลลัพธ์

Number of subarrays with n numbers are: 6

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

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

วิธีที่สอง (Second Approach)

วิธีอื่นคือสร้างอาร์เรย์สำหรับเก็บจำนวน Prefix ที่มี "i" เลขคี่ ประมวลผลทุกสมาชิก และเพิ่มจำนวนเลขคี่สำหรับทุกเลขคี่ที่พบ

เมื่อจำนวนเลขคี่เกินหรือเท่ากับ m ให้บวกจำนวนที่ตำแหน่ง (odd - m) ใน Prefix Array

เมื่อ odd มากกว่าหรือเท่ากับ m เราคำนวณจำนวน Subarray ที่สร้างได้จนถึงดัชนี และตัวเลข "odd - m" จะถูกบวกเข้า Count Variable ผลลัพธ์เก็บในตัวแปร Count หลังประมวลผลทุกสมาชิก

ตัวอย่าง

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

int main (){ 
    int array[ ] = { 1, 6, 3, 2, 5, 4 }; 
    int n = 6, m = 2, count = 0, odd = 0, i; 
    int prefix_array[n + 1] = { 0 }; 
    for (i = 0; i < n; i++){ 
        prefix_array[odd] = prefix_array[odd] + 1; 
        if (array[i] % 2 == 0) odd++; 
        if (odd >= m) count += prefix_array[odd - m]; 
    } 
    cout << "Number of subarrays with n numbers are: " << count; 
    return 0; 
}

ผลลัพธ์

Number of subarrays with n numbers are: 6

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

การเริ่มต้นตัวแปรและอาร์เรย์ด้วยค่าเริ่มต้น

int array[ 6 ] = { 1, 6, 3, 2, 5, 4 }; int n = 6, m = 2, count = 0, odd = 0, i; int prefix_array[n + 1] = { 0 };

ในนี้ เราเริ่มต้นตัวแปร n ด้วยขนาดอาร์เรย์ m ด้วยจำนวนเลขคี่ที่ต้องหา count ด้วย 0 เพื่อนับ Subarray ที่เป็นไปได้ odd ด้วย 0 และ prefix_array ขนาด n+1 ด้วย 0

การเข้าใจลูป

for (i = 0; i < n; i++){ prefix_array[odd] = prefix_array[odd] + 1; if (array[i] % 2 == 0) odd++; if (odd >= m) count += prefix_array[odd - m]; }

ในลูปนี้ เรากำหนดค่าที่ดัชนี odd ใน prefix_array[] แล้วเพิ่มตัวแปร odd ถ้าพบเลขคี่ เราหาจำนวน Subarray ที่สร้างได้จนถึงดัชนี เมื่อตัวแปร odd เท่ากับหรือมากกว่า m

สุดท้าย เราพิมพ์จำนวน Subarray ที่มีเลขคี่ m ตัว ที่เก็บในตัวแปร count และได้ผลลัพธ์

สรุป

ในบทความนี้ เราเข้าใจวิธีการหาจำนวน Subarray ที่มีเลขคี่ m ตัว จากสองวิธี

• สร้างทุก Subarray และตรวจสอบเลขคี่ m ตัว เพิ่ม Count สำหรับแต่ละ Subarray ที่พบ Time Complexity O(n²)
• วิธีมีประสิทธิภาพ คือไปผ่านแต่ละสมาชิกของอาร์เรย์ สร้าง Prefix Array และหาผลลัพธ์ด้วยความช่วยเหลือของ Prefix Array Time Complexity O(n)

หวังว่าบทความนี้จะช่วยให้เข้าใจปัญหาและวิธีแก้