Pythonで連続するk桁の数字の最大積を求める方法

2つの整数 num と k が与えられたとき、num の中で連続する k 桁の数字を取り出し、その積が最大となる組み合わせを求める問題を考えます。なお、num は必ず k 桁以上の数字を持つことが保証されています。

問題の例

例えば、num = 52689762、k = 4 の場合を考えてみましょう。このときの出力は 3024 になります。これは、4桁の連続した数字の組み合わせの中で「8 × 9 × 7 × 6 = 3024」が最大の積となるためです。

解法のアプローチ

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

• 変数 largest を 0 で初期化します
• num を 10 の (k-1) 乗で割った商が 0 より大きい間、次の処理を繰り返します
  • digits に num の下位 k 桁を取り出して代入します
  • 候補値 cand を 1 で初期化します
  • digits が 0 より大きい間、次の処理を繰り返します
    • cand に digits の最下位桁を掛け合わせます
    • cand が 0 になった場合は、それ以上計算しても結果が 0 のままであるため、ループを抜けて無駄な計算を省きます
    • digits を 10 で割って、次の桁へ処理を進めます
  • largest と cand のうち大きい方を largest に代入します
  • num を 10 で割って、探索範囲を1桁ずつずらします
• 最後に largest を返します

このアルゴリズムでは、数値の右端から1桁ずつずらしながら k 桁分の数字を取り出し、それぞれの積を計算して最大値を更新していきます。途中で 0 が出現した時点で積が必ず 0 になるため、早期にループを抜けることで計算効率を高めているのがポイントです。

実装例

それでは、実際のPythonコードを見てみましょう。

class Solution:
    def solve(self, num, k):
        largest = 0
        while num // 10 ** (k - 1) > 0:
            digits = num % 10 ** k
            cand = 1
            while digits > 0:
                cand *= digits % 10
                if cand == 0:
                    break
                digits //= 10
            largest = max(largest, cand)
            num //= 10
        return largest

ob = Solution()
num = 52689762
k = 4
print(ob.solve(num, k))

入力

52689762, 4

出力

3024

コードのポイント

• num // 10 ** (k - 1) > 0：まだ k 桁分の数字が残っているかどうかを判定する継続条件です
• num % 10 ** k：現在の num から下位 k 桁を取り出すために使っています
• cand == 0 のチェック：0 を含む組み合わせの積は必ず 0 になるため、即座に打ち切ることで効率化を実現しています

このように、剰余演算と整数除算を組み合わせることで、文字列への変換を行わずに数値のまま各桁を操作できるのが特徴です。計算量は桁数と k に依存しますが、シンプルで読みやすい実装となっています。