Đếm số chữ số 0 cuối cùng trong tích của mảng trong C++

Cho mảng Arr[] các số nguyên dương kích thước N. Mục tiêu là đếm số chữ số 0 cuối cùng (trailing zeros) trong tích của tất cả các phần tử mảng.

Ta thực hiện bằng cách đếm các thừa số của từng số. Đếm thừa số 2 và 5 của mỗi số vì tích 2 và 5 cho 10 tạo ra 1 chữ số 0 cuối. Cuối cùng, đếm nhỏ hơn giữa số lượng 2 và 5 sẽ cho số chữ số 0 cuối trong tích. Ví dụ: có 4 số 2 và 6 số 5 thì tích có 4 chữ số 0 cuối − 2×2×2×2×5×5×5×5×5×5 = 250000.

Hãy hiểu qua các ví dụ.

Đầu vào

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

Đầu ra

Số chữ số 0 cuối: 6

Giải thích

Thừa số 2 và 5 của từng phần tử: Arr[0]=2: 2^1, 5^0; Arr[1]=5: 2^1, 5^1; Arr[2]=10: 2^2, 5^2; Arr[3]=15: 2^2, 5^3; Arr[4]=20: 2^4, 5^4; Arr[5]=25: 2^4, 5^6; Arr[6]=100: 2^6, 5^8. Số 2 ít hơn nên có 6 chữ số 0 cuối.

Đầu vào

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

Đầu ra

Số chữ số 0 cuối: 5

Giải thích

Thừa số 2 và 5 của từng phần tử: Arr[0]=10: 2^1, 5^1; Arr[1]=10: 2^2, 5^2; Arr[2]=10: 2^3, 5^3; Arr[3]=10: 2^4, 5^4; Arr[4]=10: 2^5, 5^5. Số 2 và 5 bằng nhau nên 5 chữ số 0 cuối.

Phương pháp sử dụng trong chương trình dưới đây

• Nhận mảng số nguyên dương độ dài N.
• Hàm trailZeros(int arr[], int n) nhận mảng và n, trả về số chữ số 0 cuối trong tích tất cả phần tử.
• Khởi tạo biến count = 0 cho số chữ số 0.
• Hai biến twos và fives đếm thừa số 2 và 5.
• Duyệt mảng bằng vòng lặp for.
• Với mỗi phần tử nếu chia hết cho 2 hoặc 5 thì tăng twos và fives và giảm số đó đi 2 hoặc 5.
• Cuối vòng lặp kiểm tra twos và fives, lấy giá trị nhỏ hơn.
• Gán count bằng giá trị nhỏ hơn.
• Trả về count làm kết quả.

Ví dụ

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

int trailZeros(int arr[], int n) {
    int count = 0;
    int twos = 0;
    int fives = 0;
    for (int i = 0; i < n; i++) {
        while(arr[i]%2==0 || arr[i]%5==0) {
            if(arr[i]%2==0) {
                arr[i] = arr[i]/2;
                twos++;
            }
            if(arr[i]%5==0) {
                arr[i] = arr[i]/5;
                fives++;
            }
        }
    }
    count = twos < fives ? twos : fives;
    return count;
}

int main() {
    int Arr[] = { 12, 5, 15, 8, 100, 40 };
    int Length = sizeof(Arr)/sizeof(Arr[0]);
    cout << endl << "Số chữ số 0 cuối: " << trailZeros(Arr, Length);
    return 0;
}

Đầu ra

Nếu chạy mã trên sẽ cho kết quả sau:

Số chữ số 0 cuối: 5