Pythonで数値のすべての部分数（サブナンバー）が一意の桁積を持つかどうかを判定する方法

ある数値 n が与えられたとき、その数値から作られるすべての部分数（サブナンバー）の桁積（digit product）が一意であるかどうかを確認する問題を考えてみましょう。

まず用語を整理します。部分数とは、元の数値の連続する桁を取り出してできる数値のことです。n 桁の数値には n×(n+1)/2 個の部分数が存在します。たとえば、135 の部分数は「1、3、5、13、35、135」の6つです。また、桁積とは、その数値を構成する各桁の数字をすべて掛け合わせた値を指します。

問題の例

入力が n = 235 の場合を考えてみます。このとき部分数は [2, 3, 5, 23, 35, 235] となり、それぞれの桁積は次のように計算されます。

• 2 → 2
• 3 → 3
• 5 → 5
• 23 → 2 × 3 = 6
• 35 → 3 × 5 = 15
• 235 → 2 × 3 × 5 = 30

桁積は [2, 3, 5, 6, 15, 30] とすべて異なるため、出力は True になります。

解決のアプローチ

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

1. dig_prod() 関数を定義する

桁のリストを受け取り、その積を返す関数を作成します。

• product を 1 で初期化する
• digits の各要素 d に対して、product に d を掛けていく
• 最終的な product を返す

2. メイン処理を実装する

• num_str：数値 num を文字列に変換したもの
• length：num_str の長さ
• digits：長さ length のリスト（初期値は None）
• prod_set：桁積を格納するための空のセット
• i を 0 から length までループし、digits[i] に num_str[i] を整数として代入
• i と j の二重ループで、digits[i]〜digits[j] の範囲の桁積を dig_prod() で計算
• その桁積がすでに prod_set に存在すれば False を返す
• 存在しなければ prod_set に追加する
• すべての部分数を確認して重複がなければ True を返す

Pythonでの実装例

def dig_prod(digits):
    product = 1
    for d in digits:
        product *= d
    return product

def solve(num):
    num_str = str(num)
    length = len(num_str)
    digits = [None] * length
    prod_set = set()
    for i in range(0, length):
        digits[i] = int(num_str[i])
    for i in range(0, length):
        for j in range(i, length):
            item = dig_prod(digits[i:j+1])
            if item in prod_set:
                return False
            else:
                prod_set.add(item)
    return True

n = 235
print(solve(n))

入力

235

出力

True

まとめ

このアルゴリズムでは、二重ループですべての部分数を生成し、それぞれの桁積をセットに記録することで重複を検出しています。セットへの追加・検索は平均 O(1) で行えるため、一意性の判定を効率的に行えます。部分数の生成には O(n²)、各桁積の計算には最大 O(n) が必要となるため、全体の計算量は O(n³) 程度になります。桁数がそれほど大きくない数値であれば、十分実用的な手法です。