C++で特定の基数におけるパンデジタル数を判定する方法

ある基数Bにおいて、0から基数Bまでのすべての数字を含む数は、その基数における「パンデジタル数」と呼ばれます。ただし、0を含まず1から9までの数字だけで構成される数は、「ゼロなしパンデジタル数」と呼ばれます。パンデジタル数の例としては、0123456789 や 0789564312 などが挙げられます。

問題の概要

このチュートリアルでは、数値と基数が与えられたとき、その数値が指定された基数においてパンデジタル数であるかどうかを判定する問題を取り上げます。以下に入力例と出力例を示します。

入力: num = "9651723467380AZ", base = 10
出力: YES
説明: numには10進法で使用される0から9までのすべての数字が含まれているため、パンデジタル数です。

入力: num = "130264ABCDE745789", base = 16
出力: NO
説明: numには16進法で必要なF(15)が含まれていないため、パンデジタル数ではありません。

解決のためのアプローチ

この問題を解くには、重複しない値だけを保存できるセット(Set)を使用して各桁の値を格納していきます。手順は以下の通りです。

• 文字列を先頭から順に走査し、1文字ずつ処理します。

• その文字が数字(整数)か英字かを判定します。

• 英字の場合は、アルファベット上の位置に10を加算し、2桁以上の値として表現します。

• 求めた値をセットに格納します。

• 走査が完了したら、セットのサイズが基数と一致しているかどうかを確認します。

実装例

上記アプローチのC++コード

#include<bits/stdc++.h>
using namespace std;
int main(){
    int base = 10;
    char n[] = "9651723467380AZ";
    // 重複しない値を格納するためのセットを宣言
    set<int, greater<int> > s;
    // 文字列を走査
    for (int i = 0; i < strlen(n); i++){
        // 数字かどうかをチェック
        if (n[i] >= '0' && n[i] <= '9')
            s.insert(n[i]- '0');
        // 英字かどうかをチェック
        else if (n[i] - 'A' <= base - 11)
            s.insert(n[i] - 'A' + 10);
    }
    // すべての数字が揃っているか確認
    if(s.size()==base)
        cout<< "YES";
    else
        cout<< "NO";
    return 0;
}

出力結果

YES

まとめ

このチュートリアルでは、数値と基数が与えられたときに、その数値がパンデジタル数であるかどうかを判定する問題について解説しました。セットに各桁の値を挿入し、最終的なセットのサイズと基数を比較するというシンプルなアプローチを採用しました。ここで示したのはC++による実装ですが、同じロジックはC、Java、Pythonなどの他のプログラミング言語でも容易に実装できます。本チュートリアルが皆様の学習のお役に立てば幸いです。