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

• 条件while（Arr [P]％2 ==0）でwhileループを開始し、ループ内でP2++とArr[P] / 2を実行して、2の数を取得します。 P5についても同じ手順を繰り返します。

• 次に、上記の開始されたForループ内で、ネストされた2つのforループを次のように初期化します-

  for（int i =K-1; i> =0; i--）

  for（int j =0; 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){
   //Initializing each value with -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;
      // Maximal power of 2 in Arr[P]
      while (Arr[P] % 2 == 0){
         P2++;
         Arr[P] /= 2;
      }
      // Maximal power of 2 in Arr[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++)
         // If subset[i][j] is not calculated.
         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;
}
//Main function
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