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

在以下程序中使用的方法如下

• 在启动功能之前，在顶部#define M5 100。

• 在函数中，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循环，如下所示：

  对于（int i = K-1; i> = 0; i--）

  对于（int j = 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