【Python】開始・終了範囲内の連続増加数をすべて検索するプログラムの作成方法

問題の概要

2つの整数 start と end が与えられたとき、範囲 [start, end]（両端を含む）に存在する整数のうち、各桁が連続して増加している数だけをすべて抽出し、昇順にソートされたリストとして返すプログラムを作成します。

ここでいう「連続して増加する数」とは、たとえば 5678 のように、上の桁から下の桁へ向かって数字が1ずつ増えていく数のことです。一方、169 のように途中で桁が飛んでいる数は条件を満たしません。

例として、start = 10、end = 150 が入力された場合の出力は次のようになります。

[12, 23, 34, 45, 56, 67, 78, 89, 123]

解法のアプローチ

この問題の鍵となるのは、「連続して増加する数」は必ず文字列 "123456789" の部分文字列として表せるという性質です。実際、そのような数は全体でも高々45個しか存在しないため、候補を全件生成して範囲内に収まっているかどうかを判定すれば十分です。

アルゴリズムの手順

• s := 文字列 "123456789" を用意する
• a := 結果を格納する空のリスト
• i を 0 から 8 まで繰り返す：
  • j を i + 1 から 9 まで繰り返す：
    • x := s の i 番目から j-1 番目までの部分文字列を整数に変換した値
    • もし start ≤ x ≤ end であれば、x を a に追加する
• 最後に a をソートして返す

Pythonでの実装例

以下のコードで処理内容をより具体的に確認できます。

def solve(start, end):
    s = "123456789"
    a = []
    for i in range(9):
        for j in range(i + 1, 10):
            x = int(s[i:j])
            if start <= x <= end:
                a += (x,)
    return sorted(a)

start = 10
end = 150
print(solve(start, end))

入力

10, 150

出力

[12, 23, 34, 45, 56, 67, 78, 89, 123]

計算量について

外側のループは9回、内側のループも最大9回しか回らないため、生成される候補は長さ9の文字列の部分文字列の総数である45個以下です。つまり、start と end の差がどれほど大きくても、計算量はほぼ一定（O(1)）であり、非常に広い範囲が与えられた場合でも高速に動作します。