นับจำนวนศูนย์ต่อท้ายในผลคูณของอาร์เรย์ใน C++

ภาพรวมปัญหา

ให้อาร์เรย์ Arr[] ของจำนวนเต็มบวกขนาด N ต้องการหาจำนวนศูนย์ต่อท้าย (trailing zeros) ในผลคูณของทุกสมาชิกในอาร์เรย์

หลักการคำนวณ

ศูนย์ต่อท้ายเกิดจากตัวประกอบ 10 = 2 × 5

• นับจำนวนตัวประกอบ 2 และ 5 ในการแยกตัวประกอบของทุกจำนวน
• จำนวนศูนย์ต่อท้าย = min(จำนวน 2, จำนวน 5)
• ตัวอย่าง: 2⁴ × 5⁶ = 16 × 15625 = 250000 มี 4 ศูนย์ต่อท้าย

ตัวอย่าง

Input: Arr[] = {2, 5, 10, 15, 20, 25, 100}

Output: 6

คำอธิบาย: รวม 2 ได้ 6 ตัว, 5 ได้ 8 ตัว → min(6,8) = 6

Input: Arr[] = {10, 10, 10, 10, 10}

Output: 5

คำอธิบาย: แต่ละ 10 มี 2 และ 5 ตัวละ 1 รวม 5 คู่ → 5 ศูนย์

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

1. ฟังก์ชัน trailZeros(int arr[], int n)
2. ตัวแปร twos = 0, fives = 0
3. วนลูปแต่ละสมาชิกในอาร์เรย์
4. ใช้ while loop แยกตัวประกอบ 2 และ 5 ออกจนหมด
5. คืนค่า min(twos, fives)

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

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

int trailZeros(int arr[], int n) {
    int twos = 0, fives = 0;
    
    for (int i = 0; i < n; i++) {
        int num = arr[i];
        while (num % 2 == 0) {
            twos++;
            num /= 2;
        }
        while (num % 5 == 0) {
            fives++;
            num /= 5;
        }
    }
    return min(twos, fives);
}

int main() {
    int Arr[] = {12, 5, 15, 8, 100, 40};
    int Length = sizeof(Arr) / sizeof(Arr[0]);
    cout << "Number of trailing zeroes: " << trailZeros(Arr, Length);
    return 0;
}

ผลลัพธ์

Number of trailing zeroes: 5

ความซับซ้อน

• เวลา: O(N × log max(arr[i])) - แต่ละจำนวนหาร 2 และ 5 ซ้ำๆ
• พื้นที่: O(1)

การประยุกต์ใช้

เทคนิคนี้ใช้กันอย่างกว้างขวางในการหาจำนวนศูนย์ต่อท้ายของแฟกทอเรียล (N!) ด้วย