C++でM個の数字から作れる、5で割り切れるN桁の数の個数を求める方法

ある整数Nと、M個の数字からなる配列が与えられます。このとき、与えられたM個の数字を使って作成できるN桁の数のうち、5で割り切れるものの個数を求めるのが本記事のテーマです。

まず、入力と出力の例を見ながら、問題の内容を確認していきましょう。

入力 −

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

出力 −

2

この場合、5で割り切れるN桁の数は「35」と「65」の2つです。続いて、別の例を見てみます。

入力 −

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

出力 −

1

配列の中で5で割り切れる1桁の数は「5」だけなので、答えは1となります。つまりこの問題は、「与えられたM個の数字から作れるN桁の数のうち、5で割り切れるものが何個あるかを求める」という課題です。

ここで重要なのは、5で割り切れる数は必ず末尾が0または5になるという性質です。この性質を利用してアルゴリズムを組み立てます。

アルゴリズム

• まず、配列の中に0と5が含まれているかどうかを確認します。
• 0と5の両方が存在する場合、一の位に置ける数字は2通りあります。
  • カウントを2で初期化します。
  • 残りの桁には、m−1、m−2、m−3…というように、埋めるごとに候補が1つずつ減っていきます。
  • 0からn−1まで繰り返すループを作成します。
    • 配列のサイズ（m）を1ずつ減らします。
    • その値をカウントに掛け合わせます。
• 0または5のどちらか片方だけが存在する場合、一の位に置ける数字は1通りです。
  • カウントを1で初期化します。
  • 残りの桁については上記と同様に、m−1、m−2、…の順で候補の数を掛け合わせていきます。
• 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