หาผลคูณองค์ประกอบในอาร์เรย์ที่หาร K ลงตัวใน C++

ได้รับอาร์เรย์ arr[n] และจำนวนเต็ม K งานคือหาผลคูณขององค์ประกอบทั้งหมดที่หาร K ลงตัว

ตัวอย่าง

ตัวอย่างที่ 1

Input: arr[] = {10, 11, 55, 2, 6, 7}, K = 11

หาร 11 ลงตัว: 11, 55

ผลคูณ: 11 × 55 = 605

ตัวอย่างที่ 2

Input: arr[] = {9, 8, 7, 6, 3}, K = 3

หาร 3 ลงตัว: 9, 6, 3

ผลคูณ: 9 × 6 × 3 = 162

แนวทางแก้ปัญหา

1. ตั้งค่า product = 1
2. วนทุกองค์ประกอบในอาร์เรย์
3. ถ้า arr[i] % K == 0 ให้ product *= arr[i]
4. คืนค่า product (หากไม่มีตัวใดหารลงตัว คืน 1 หรือ 0 ตาม spec)

ตัวอย่างโค้ด

#include <iostream>
#include <vector>
using namespace std;

long long productDivisibleByK(const vector<int>& arr, int K) {
    long long product = 1;
    bool found = false;
    
    for (int x : arr) {
        if (x % K == 0) {
            product *= x;
            found = true;
        }
    }
    
    return found ? product : 0;  // คืน 0 หากไม่มีตัวใดหารลงตัว
}

int main() {
    vector<int> arr1 = {10, 11, 55, 2, 6, 7};
    int K = 11;
    cout << "Product divisible by " << K << ": " 
         << productDivisibleByK(arr1, K) << endl;  // 605
    
    vector<int> arr2 = {9, 8, 7, 6, 3};
    K = 3;
    cout << "Product divisible by " << K << ": " 
         << productDivisibleByK(arr2, K) << endl;  // 162
    
    return 0;
}

กรณีพิเศษและข้อควรระวัง

1. ผลคูณอาจล้น (Overflow)

ใช้ long long (64-bit) หรือ __int128 หรือ Modulo

const long long MOD = 1000000007LL;
product = (product * x) % MOD;

2. K = 0

การหารด้วย 0 ไม่ได้นิยาม ควรตรวจสอบ if (K == 0) return 0;

3. ค่าติดลบ

ใน C++ -6 % 3 == 0 (หารลงตัว) แต่ -6 % 4 == -2 (ไม่ใช่ 0) – ใช้ x % K == 0 ได้ถูกต้องสำหรับ negative ด้วย

4. ไม่มีองค์ประกอบไหนหารลงตัว

ควรคืนค่า 0 (แทน 1) เพื่อแยกจากกรณีที่มีแค่ 1 ตัวที่เป็น 1

ความซับซ้อน

• เวลา: O(N) – วนอาร์เรย์ 1 รอบ
• พื้นที่: O(1)

ขยายความ: นับจำนวนแทนผลคูณ

int countDivisibleByK(const vector<int>& arr, int K) {
    int count = 0;
    for (int x : arr) if (x % K == 0) count++;
    return count;
}