C++のM桁から形成される5で割り切れるN桁の数値

M桁の配列とともに数値Nを指定しました。私たちの仕事は、5で割り切れる与えられたM桁から形成されたn桁の数を見つけることです。

問題の入力と出力を理解するために、いくつかの例を見てみましょう。

で-

N = 2
M = 3
arr = {5, 6, 3}

アウト-

2

5で割り切れる2つのN桁の数字35と65があります。別の例を見てみましょう。

入力-

N = 1
M = 7
arr = {2, 3, 4, 5, 6, 7, 8}

出力-

1

与えられた配列には、5で割り切れる1桁の数が1つしかないので、私たちのタスクは、5で割り切れるN桁の与えられた数から形成できる数を見つけることです。

5で割り切れるには、数字の0または5で終わる必要があります。アルゴリズムを見てみましょう

アルゴリズム

• 指定された配列の0と5を確認します。 2. 0と5の両方がある場合、単位の場所に数字を配置する方法は2つあります。それ以外の場合は、数字を配置する単一の方法があります。
  • カウントを2に初期化します。
  • これで、残りの場所には、それぞれm-1、m-2、m-3、...n個の方法で埋めることができます。
  • 0からn-1まで繰り返すループを記述します。
    • 配列のそのサイズをデクリメントします。
    • カウントを掛けます。
• 0または5の数字が1つある場合、単位の場所に数字を配置する方法は1つだけです。
  • カウントを2に初期化します。
  • これで、残りの場所には、それぞれm-1、m-2、m-3、...n個の方法で埋めることができます。
  • 0からn-1まで繰り返すループを記述します。
    • 配列のそのサイズをデクリメントします。
    • カウントを掛けます。
• 0または5の数字がない場合は、5で割り切れる数を作成できます。その場合は-1を返します。

実装

以下は、C++での上記のアルゴリズムの実装です

#include <bits/stdc++.h>

using namespace std;

int numbers(int n, int m, int arr[]) {
   bool isZeroPresent = false, isFivePresent = false;
   int numbersCount = 0;
   if (m < n) {
      return -1;
   }
   for (int i = 0; i < m; i++) {
      if (arr[i] == 0) {
         isZeroPresent = true;
      }
      if (arr[i] == 5) {
         isFivePresent = true;
      }
   }
   if (isZeroPresent && isFivePresent) {
      numbersCount = 2;
      for (int i = 0; i < n - 1; i++) {
         m--;
         numbersCount = numbersCount * m;
      }
   } else if (isZeroPresent || isFivePresent) {
      numbersCount = 1;
      for (int i = 0; i < n - 1; i++) {
         m--;
         numbersCount = numbersCount * m;
      }
   } else {
      return -1;
   }
   return numbersCount;
}
int main() {
   int arr[] = {5, 6, 3};
   cout << numbers(2, 3, arr) << endl;
   return 0;
}

出力

上記のコードを実行すると、次の結果が得られます。

2