Chúng ta được cung cấp một mảng Arr [] gồm các số nguyên dương có kích thước N. Mục đích là đếm số lượng các số 0 ở cuối có trong tích của tất cả các phần tử của mảng.
Chúng tôi sẽ làm điều này bằng cách đếm các thừa số của mỗi số. Chúng ta sẽ đếm 2 và 5 là thừa số của mỗi số vì tích của 2 và 5 là 10 sẽ cho 1 dấu 0. Cuối cùng, số nào nhỏ hơn sẽ tính được các số 0 ở cuối trong tích. Nếu chúng ta có 4 chữ 2 và 6 chữ 5 thì sẽ có 4 số 0 ở cuối sản phẩm - 2 * 2 * 2 * 2 * 5 * 5 * 5 * 5 * 5 * 5 =250000
Hãy cùng hiểu với các ví dụ.
Đầu vào
Arr[] = { 2, 5, 10, 15, 20, 25, 100 } Đầu ra
Number of trailing zeroes : 6
Giải thích
Factors 2 and 5 of each element of Arr[]: Arr[0] = 2 : 2 twos=1, fives=0 Arr[1] = 5 : 5 twos=1, fives=1 Arr[2] = 10 : 2*5 twos=2, fives=2 Arr[3] = 15 : 3*5 twos=2, fives=3 Arr[4] = 20 : 2*2*5 twos=4, fives=4 Arr[5] = 25 : 5*5 twos=4, fives=6 Arr[6] = 100 : 2*2*5*5 twos=6, fives=8 Count of 2 is less so trailing zeroes will be 6.
Đầu vào
Arr[] = { 10,10,10,10,10 } Đầu ra
Number of trailing zeroes : 5
Giải thích
Factors 2 and 5 of each element of Arr[]: Arr[0] = 10 : 2*5 twos=1, fives=1 Arr[1] = 10 : 2*5 twos=2, fives=2 Arr[2] = 10 : 2*5 twos=3, fives=3 Arr[3] = 10 : 3*5 twos=4, fives=4 Arr[4] = 10 : 2*5 twos=5, fives=5 Count of 2 and 5 is equal so trailing zeroes will be 5.
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
-
Chúng ta lấy một mảng các số nguyên dương có độ dài N..
-
Hàm trailZeros (int arr [], int n) nhận mảng và n làm đầu vào và trả về số lượng các số 0 ở cuối trong tích của tất cả các phần tử.
-
Lấy số lượng biến ban đầu là 0 cho các số 0.
-
Lấy hai biến twos và fives làm hệ số đếm 2 và 5.
-
Traverse mảng sử dụng vòng lặp for.
-
Đối với mỗi phần tử nếu nó chia hết cho 2 hoặc 5 thì tăng hai phần tử và giảm nó đi 2 hoặc 5.
-
Vào cuối vòng lặp for, hãy kiểm tra giá trị của twos và fives tùy theo giá trị nào nhỏ hơn.
-
Khởi tạo số lượng với số thấp hơn trong số hai.
-
Trả về kết quả là số lượng.
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<< "Number of trailing zeroes : "<<trailZeros(Arr,Length);
return 0;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Number of trailing zeroes : 5