C++で指定した範囲内の「各桁がすべて異なる」整数を検索する方法

この記事では、2つの整数 l と r が与えられたとき、その範囲（両端を含む）に存在する「各桁の数字がすべて異なる」整数 x を見つけるC++のプログラムを紹介します。

例えば、入力が l = 211、r = 230 の場合、出力は 213 となります。211は「1」が重複しているため条件を満たしませんが、213は各桁（2・1・3）がすべて異なるため有効な答えです。

解法のアプローチ

この問題は、以下の手順で解くことができます。

1. l から r までの各整数 k を順番に調べます。
2. k を文字列に変換します。
3. 文字列の各文字（桁）をセット（set）に挿入します。セットは重複を許さないため、同じ数字は自動的に1つにまとめられます。
4. セットのサイズと元の文字列の長さが一致していれば、すべての桁が異なることを意味するため、その数値を答えとして返します。
5. 範囲全体を調べて該当する数値が見つからなかった場合は、「-1」を返します。

アルゴリズムの擬似コード

for initialize k := l, when k <= r, update (increase k by 1), do:
    h := convert k to string
    Define one set s
    for initialize i := 0, when i < size of h, update (increase i by 1), do:
        insert h[i] into s
    if size of s is same as size of h, then:
        return h
return "-1"

C++での実装例

実際のC++コードは以下の通りです。

#include <bits/stdc++.h>
using namespace std;

string solve(int l, int r) {
    for (int k = l; k <= r; k++) {
        string h = to_string(k);
        set<char> s;
        for (int i = 0; i < h.size(); i++)
            s.insert(h[i]);
        if (s.size() == h.size()) {
            return h;
        }
    }
    return "-1";
}
int main() {
    int l = 211;
    int r = 230;
    cout << solve(l, r) << endl;
}

実行結果

入力

211, 230

出力

213

計算量について

このアルゴリズムの時間計算量は O((r − l + 1) × d) です。ここで d は数値の桁数（最大でも10程度）を表します。検索範囲が広すぎない場合には十分に高速に動作しますが、範囲が非常に大きい場合はより効率的な手法を検討する必要があります。