Pythonで桁を並べ替えて2の累乗を作れるか判定するプログラム

正の整数 N が与えられたとします。この数の桁を任意の順序に並べ替え（元の順序のままでも可）、先頭の桁が0にならないようにします。そして、その結果得られる数が2の累乗になるようにできるかどうかを判定する必要があります。

例えば、入力が N = 812 の場合、出力は True となります。これは「812」の桁を並べ替えると「128」（= 2⁷）を作れるためです。

解法のアプローチ

この問題を解く鍵となるのは、「桁を並べ替えた数同士は、ソート後の桁の並びが必ず一致する」という性質です。つまり、ある数がNの桁を並べ替えたものであるかを調べるには、両者を文字列に変換して文字をソートし、一致するかどうかを比較すればよいのです。

具体的には、以下の手順で解くことができます。

• 変数 i を1で初期化します。
• i が 1,000,000,000 以下である限り、以下を繰り返します。
  • i を文字列に変換し、その文字をソートしたものを s とします。
  • n を文字列に変換し、その文字をソートしたものを t とします。
  • s と t が一致する場合、True を返します。
  • i を2倍します。
• ループが終了しても一致するものが見つからなければ、False を返します。

2の累乗は32ビット整数の範囲で最大でも 2³⁰ = 1,073,741,824 なので、上限を10億（1,000,000,000）とすれば、すべての候補を網羅できます。

実装例

それでは、実際のPythonコードを見て、より深く理解しましょう。

def solve(n):
   i = 1
   while i <= 1000000000:
      s = str(i)
      s = ''.join(sorted(s))
      t = str(n)
      t = ''.join(sorted(t))
      if s == t:
         return True
      i = i * 2
   return False

N = 812
print(solve(N))

入力

812

出力

True

コードの解説

このプログラムでは、まず i = 1 から始めて、2の累乗（1, 2, 4, 8, 16, ...）を順番に生成していきます。それぞれの累乗について、その数字を文字列に変換してソートし、入力 N を同様にソートした結果と比較します。

N = 812 の場合、桁をソートすると "128" となります。一方、2の累乗を順に調べていくと、i = 128 のときのソート結果も "128" となり、両者が一致します。したがって、True が返されます。

計算量について

2の累乗の候補は高々31個（2⁰ から 2³⁰）しかないため、各候補に対する文字列のソートと比較の処理を合わせても、全体として非常に効率的に動作します。時間計算量は O(31 × d log d)（d は桁数）程度であり、実質的にはほぼ定数時間で処理が完了すると言えます。