题目描述

从正整数 N 开始，我们按任何顺序（包括原始顺序）将数字重新排序，注意其前导数字不能为零。

如果我们可以通过上述方式得到 2 的幂，返回 true；否则，返回 false。

样例

输入：1
输出：true

输入：10
输出：false

输入：16
输出：true

输入：24
输出：false

输入：46
输出：true

注意

• 1 <= N <= 10^9

算法

(枚举) $O(\log ^2 N)$

• 从 1 开始枚举 2 的幂次，直到 N * 10，逐一检查是否符合要求。
• 首先检查长度是否一致，然后可以先用 vis 数组存下 N 中每个数字出现了多少次，然后分别统计 2 的幂次的数字串中每个数字的个数，查看是否一致。

时间复杂度

• 共需要 $O(\log N)$ 次枚举，每次用 $O(\log N)$ 的时间内判定，故时间复杂度为 $O(\log ^2 N)$。

C++ 代码

class Solution {
public:

    bool check(const vector<int> &vis, const string &t) {
         vector<int> used(10, 0);
         for (int i = 0; i < t.length(); i++)
             used[t[i] - '0']++;

         for (int i = 0; i < 10; i++)
             if (vis[i] != used[i])
                 return false;

        return true;
    }

    bool reorderedPowerOf2(int N) {
        string s = to_string(N);
        vector<int> vis(10, 0);

        for (int i = 0; i < s.length(); i++)
            vis[s[i] - '0']++;

        for (int i = 0; i < 31; i++) {
            string t = to_string(1 << i);
            if (s.length() == t.length() && check(vis, t))
                return true;
        }

        return false;
    }
};