C ++中大小为k的子集的乘积中的最大尾随零数
给定任务是找到大小为N的给定数组的大小为K的子集的乘积中的最大尾随零。
现在让我们使用示例了解我们必须做的事情-
输入−Arr[]={5，20，2}，K=2
输出-2
说明-可以创建大小为2的总共3个子集。
[5，20]的乘积为100。
[20，2]的乘积为40。
[5，2]的乘积为10。
100的最大尾随零位数=2。因此，答案为2。
输入−Arr[]={60，40，25}，K=2
输出-3
在以下程序中使用的方法如下
在启动功能之前，在顶部#defineM5100。
在函数中，MaxZeros()创建一个2D数组Sub[K+1][M5+5]，并使用-1初始化其每个值，并将Sub[0][0]=0设置为零；
从P=0直到P<N循环，并在循环内部初始化int类型的P2=0和P5=0，这两种类型将分别用于存储给定数量的2s和5s。
在条件while（Arr[P]％2==0）中启动一个while循环，并在循环内部执行P2++和Arr[P]/2以获得2的数量。对P5重复相同的步骤。
然后在上面启动的For循环中，另外初始化两个嵌套的for循环，如下所示：
对于（inti=K-1;i>=0;i--）
对于（intj=0;j<M5;j++）
在这些循环中检查if（Sub[i][j]！=-1），如果为true，则将Sub[i+1][j+P5]=max（Sub[i+1];[j+P5]，Sub[i][j]+P2）；
示例
#include <bits/stdc++.h>
using namespace std;
#define M5 100
int MaxZeros(int* Arr, int N, int K){
//用-1初始化每个值；
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;
//Arr中2的最大幂[P]
while (Arr[P] % 2 == 0){
P2++;
Arr[P] /= 2;
}
//Arr中2的最大幂[P]
while (Arr[P] % 5 == 0) {
P5++;
Arr[P] /= 5;
}
/* We can collect 2s by checking first i numbers and taking their j with total power of 5*/
for (int i = K - 1; i >= 0; i--)
for (int j = 0; j < M5; j++)
//如果不计算subset[i][j]。
if (Sub[i][j] != -1)
Sub[i + 1][j + P5] = max(Sub[i + 1][j + P5], Sub[i][j] + P2);
}
/* Taking minimum of 5 or 2 and maximizing the result*/
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