Pythonで指定した範囲内の特別な数の個数を求めるプログラム

整数の範囲が与えられ、その範囲内に含まれる特別な数の個数を求めることを考えます。ここでいう特別な数とは、10進表現で1桁しか持たない正の整数のことです。さらに、2桁以上の数であっても、その数が自身の桁数で割り切れ、かつ商がそれ自体特別な数である場合には、特別な数とみなされます。

この条件をもとに、与えられた範囲 (left_limit, right_limit) 内に存在する特別な数の個数を返します。

例として、left_limit = 5、right_limit = 30 が入力された場合、出力は 13 になります。

この範囲内の特別な数は次の13個です。
5, 6, 7, 8, 9, 10, 12, 14, 16, 18, 20, 24, 28

解法のアプローチ

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

• right_limit が 10 未満の場合は、right_limit − left_limit + 1 を返します（1桁の正の整数はすべて特別な数であるため）。
• len_right := 文字列化した right_limit の文字数
• number_list := [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 16, 18] で初期化します
• j を 2 から len_right + 1 まで繰り返します。
  • number_list 内の各要素 k について、temp1 := k × j を計算します
  • temp1 を文字列化した長さが j と一致する場合、temp1 を number_list の末尾に追加します
  • そうでなく、文字列化した長さが j より大きい場合は内側のループを抜けます
• number_list の末尾の要素が right_limit 以上になったら、外側のループを抜けます
• number_list から重複する値を削除し、ソートします
• count := 0 と初期化します
• number_list 内の各要素 temp2 について、left_limit ≤ temp2 ≤ right_limit を満たす場合は count を 1 増やします
• 最後に count を返します

実装例

理解を深めるために、以下のPython実装を見てみましょう。

def strange(left_limit, right_limit):
    if right_limit < 10:
        return right_limit - left_limit + 1
    len_right = len(str(right_limit))
    number_list = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 16, 18]
    for j in range(2, len_right + 1):
        for k in number_list:
            temp1 = k * j
            if len(str(temp1)) == j:
                number_list.append(temp1)
            elif len(str(temp1)) > j:
                break
        if number_list[-1] >= right_limit:
            break
    number_list = sorted(set(number_list))
    count = 0
    for temp2 in number_list:
        if left_limit <= temp2 <= right_limit:
            count += 1
    return count

print(strange(5, 30))

入力

5, 30

出力

13

アルゴリズムのポイント

この手法の鍵は、「既知の特別な数 k に対して、k × j（j は目標の桁数）がちょうど j 桁の数になれば、それは新しい特別な数になる」という性質です。なぜなら、k × j の桁数は j であり、これを j で割った商は k、つまりすでに特別な数であることが保証されているからです。

この性質を利用すれば、1桁の特別な数から出発して、桁数の小さいものから順に大きい桁の特別な数を次々と生成できます。候補リストが right_limit を超えた時点で生成を打ち切り、最後に範囲内に含まれる個数を数えるだけでよいため、非常に効率的に答えを求められます。