C++で桁を並べ替えて2の累乗にできるか判定するアルゴリズム

正の整数 N が与えられたとします。この数の桁を任意の順序に並べ替え(元の順序も含む)、先頭の桁が 0 以外になるようにします。そのうえで、並べ替えた結果が 2 の累乗になるような並べ方が存在するかどうかを判定します。たとえば、数値が 46 の場合、答えは true となります。

解法の考え方

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

• count というメソッドを定義します。引数として x を受け取ります。

• ret := 0 で初期化します。

• x が 0 でない間、次の処理を繰り返します。

  • ret := ret + 10 ^ (x の最下位桁)

  • x := x / 10

• ret を返します。

• メインの処理では、以下を実行します。

• x := count(N) を計算します。

• i を 0 から 31 までループさせます。

  • count(2^i) == x であれば true を返します。

• どれとも一致しなければ false を返します。

ここで使われる count 関数は、各桁の数字 d に対して 10^d を加算していくことで、その数値の「桁構成のシグネチャ」を生成します。同じ数字の組み合わせ(マルチセット)を持つ数値同士は必ず同じシグネチャになるため、N のシグネチャと 2 の累乗(2⁰ 〜 2³¹)のシグネチャを比較するだけで、桁の並べ替えによって一致させられるかどうかを高速に判定できます。

理解を深めるために、以下の実装例を見てみましょう。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int count(int x){
        int ret = 0;
        while(x){
            ret += pow(10, x % 10);
            x /= 10;
        }
        return ret;
    }
    bool reorderedPowerOf2(int N) {
        int x = count(N);
        for(int i = 0; i < 32; i++){
            if(count(1 << i) == x) return true;
        }
        return false;
    }
};
main(){
    Solution ob;
    cout << (ob.reorderedPowerOf2(812));
}

入力

812

出力

1

この例では、812 の桁を並べ替えると 128(= 2⁷)を作ることができるため、出力は 1(true)となります。count の呼び出しはそれぞれ桁数に比例したコストしかかからず、比較対象も 2⁰ から 2³¹ までの 32 個だけなので、全体の計算量は O((log N)²) 程度に抑えられ、非常に効率的な手法といえます。