จำนวนศูนย์ท้ายสูงสุดในผลคูณของเซตย่อยขนาด k ใน C++

โจทย์: หาจำนวนศูนย์ท้าย (trailing zeros) สูงสุดในผลคูณของเซตย่อย (subsets) ขนาด K จากอาร์เรย์ขนาด N

ตัวอย่าง

Input: Arr[] = {5, 20, 2}, K = 2
Output: 2

คำอธิบาย: เซตย่อยขนาด 2 มี 3 ชุด: - [5, 20] → 100 (2 ศูนย์ท้าย) - [20, 2] → 40 (1 ศูนย์ท้าย) - [5, 2] → 10 (1 ศูนย์ท้าย) ค่าสูงสุดคือ 2

Input: Arr[] = {60, 40, 25}, K = 2
Output: 3

แนวทางแก้ปัญหา (Dynamic Programming)

จำนวนศูนย์ท้ายขึ้นอยู่กับจำนวนคู่ของปัจจัย 2 และ 5 (เพราะ 10 = 2 × 5) ใช้ DP เก็บจำนวนปัจจัย 2 สูงสุดสำหรับแต่ละจำนวนปัจจัย 5

1. กำหนด M5 = 100 (ขีดจำกัดปัจจัย 5)
2. สร้างตาราง Sub[K+1][M5+5] เริ่มต้น -1, Sub[0][0] = 0
3. แยกตัวประกอบแต่ละจำนวนในอาร์เรย์ หาจำนวน 2 (P2) และ 5 (P5)
4. อัปเดตตาราง DP แบบ bottom-up
5. คำตอบ = max(min(i, Sub[K][i])) สำหรับทุก i

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

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

int MaxZeros(int* Arr, int N, int K) {
    int Sub[K+1][M5+5];
    memset(Sub, -1, sizeof(Sub));
    Sub[0][0] = 0;
    
    for (int P = 0; P < N; P++) {
        int P2 = 0, P5 = 0;
        
        while (Arr[P] % 2 == 0) { P2++; Arr[P] /= 2; }
        while (Arr[P] % 5 == 0) { P5++; Arr[P] /= 5; }
        
        for (int i = K - 1; i >= 0; i--)
            for (int j = 0; j < M5; j++)
                if (Sub[i][j] != -1)
                    Sub[i + 1][j + P5] = max(Sub[i + 1][j + P5], Sub[i][j] + P2);
    }
    
    int ans = 0;
    for (int i = 0; i < M5; i++)
        ans = max(ans, min(i, Sub[K][i]));
    
    return ans;
}

int main() {
    int Arr[] = { 60, 40, 25 };
    int K = 2;
    int N = sizeof(Arr) / sizeof(Arr[0]);
    cout << MaxZeros(Arr, N, K);
    return 0;
}

ผลลัพธ์

3