数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中数组乘积中尾随零的个数
给定一个大小为 N 的正整数数组 Arr[]。目标是计算数组所有元素的乘积中存在的尾随零的个数。
我们将通过计算每个数字的因子来做到这一点。我们将 2 和 5 作为每个数字的因子进行计数，因为 2 和 5 的乘积是 10，它产生 1 个尾随 0。最后，较小的计数决定了乘积中尾随零的个数。如果我们有 4 个 2 和 6 个 5，那么乘积中将有 4 个尾随零 - 2*2*2*2*5*5*5*5*5*5= 250000
让我们通过示例来理解。
输入
Arr[] = { 2, 5, 10, 15, 20, 25, 100 }输出
Number of trailing zeroes : 6
解释
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.
输入
Arr[] = { 10,10,10,10,10 }输出
Number of trailing zeroes : 5
解释
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.
下面程序中使用的方案如下
我们获取一个长度为 N 的正整数数组。
函数 trailZeros(int arr[],int n) 以数组和 n 作为输入，并返回所有元素乘积中尾随零的个数。
将初始变量 count 设为 0，表示零的个数。
将两个变量 twos 和 fives 作为因子中 2 和 5 的个数。
使用 for 循环遍历数组。
对于每个元素，如果它可以被 2 或 5 整除，则递增 twos 和 fives，并将其分别减少 2 或 5。
在 for 循环结束时，检查 twos 和 fives 的值，取较小的那个。
将 count 初始化为两者中较小的那个。
返回 count 作为结果。
示例
#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;
}输出
如果我们运行以上代码，它将生成以下输出：
Number of trailing zeroes : 5
更新于: 2020-10-31
293 次浏览
广告