PythonでKの倍数となる最小の「1のみの整数」の桁数を求めるアルゴリズム

問題概要

正の整数Kが与えられたとき、「各桁がすべて1で構成され、かつKで割り切れる」ような最小の正の整数Nを求めます。答えとなるNの桁数を返し、そのようなNが存在しない場合は-1を返します。

例えば、入力が3の場合、出力は3になります。これは、条件を満たす最小の整数が N = 111 だからです。

解法のアプローチ

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

• Kが偶数、または5で割り切れる場合は-1を返します。1のみで構成される整数の一の位は常に1であるため、偶数にも5の倍数にもなり得ないからです。
• 変数 r を0、N を1で初期化します。
• i を1からK+1まで繰り返します。
  • r := (r * 10 + 1) mod K を計算します。
  • r が0になった時点で i を返します。

このアルゴリズムのポイントは、巨大な整数Nを実際に構築する必要がないことです。「既存の数に1を右側に付け加える」操作は「元の数 × 10 + 1」と等しいため、剰余演算を用いて余りのみを逐次更新すれば十分です。これにより、大きな数のオーバーフローや計算コストを気にせず処理できます。

さらに、鳩の巣原理により、答えが存在する場合、その桁数は必ずK以下になることが示されています。したがって、ループをK回まで回せば答えが見つかるか、存在しないと判断できます。

実装例

class Solution(object):
    def smallestRepunitDivByK(self, K):
        if K % 2 == 0 or K % 5 == 0:
            return -1
        r = 0
        N = 1
        for i in range(1, K + 1):
            r = (r * 10 + 1) % K
            if r == 0:
                return i

ob = Solution()
print(ob.smallestRepunitDivByK(11))

入力

11

出力

2

この例では、K = 11 のとき、11で割り切れる最小の「1のみの整数」は 11 です。その桁数は2であるため、出力は2となります。