【Python】1からnまでの整数に含まれる特定の数字の出現回数を求める方法

2つの正の整数 n と d が与えられたとします。ここで、d は 0〜9 のいずれかの1桁の数字です。この課題では、1 から n までの整数の中に、数字 d が合計で何回出現するかを求めます。

例えば、入力が n = 45、d = 5 の場合、出力は 5 となります。

その理由は、1〜45 の範囲内で「5」という数字を含む数が以下の5つ存在するためです。

[5, 15, 25, 35, 45]

解法のアプローチ

この問題は、全数を1つずつ調べるよりも、再帰的な計算によって効率よく求めることができます。手順は以下の通りです。

• 関数 solve() を定義します。引数として n と d を受け取ります。
• n が 0 未満の場合は 0 を返します(再帰の終了条件)。
• k を「n ÷ 10 の切り捨て値 − 1」として計算します。
• ans を「solve(k, d) × 10 + k + 1」として計算します。これにより、それより上の桁の範囲での出現回数を再帰的に求めます。
• d が 0 の場合は、ans から 1 を引きます(0 は先頭の桁には現れないための補正)。
• m を「n ÷ 10 の切り捨て値 × 10」(つまり現在の10の区切りの開始値)とします。
• m が n 以下である間、次の処理を繰り返します。
  • ans に「m を文字列に変換した際の d の出現回数」を加算します。
  • m を 1 増やします。
• 最後に ans を返します。

実装例

以下が実際のPythonコードです。

class Solution:
    def solve(self, n, d):
        if n < 0:
            return 0
        k = n // 10 - 1
        ans = self.solve(k, d) * 10 + k + 1
        if d == 0:
            ans -= 1
        m = n // 10 * 10
        while m <= n:
            ans += str(m).count(str(d))
            m += 1
        return ans

ob = Solution()
print(ob.solve(45, 5))

入力

45, 5

出力

5

コードのポイント

• 再帰構造: 上位の桁の範囲(例：1〜39)に対する出現回数を再帰的に求めることで、大きな n でも高速に計算できます。
• 端数処理: 10で割った余りの部分(40〜45など)だけをループで直接カウントすることで、無駄な計算を避けています。
• d = 0 への対応: 「0」は数の先頭には現れないため、専用の補正処理が必要になる点に注意しましょう。

このように、再帰と文字列カウントを組み合わせることで、1からnまでの範囲に含まれる任意の数字の出現回数を効率的に求めることができます。