Problem

Starting with a positive integer N, we reorder the digits in any order (including the original order) such that the leading digit is not zero.

Return true if and only if we can do this in a way such that the resulting number is a power of 2.

Example 1:

Input: 1
Output: true

Example 2:

Input: 10
Output: false

Example 3:

Input: 16
Output: true

Example 4:

Input: 24
Output: false

Example 5:

1 2	<strong>Input: </strong><span id="example-input-5-1">46</span> <strong>Output: </strong><span id="example-output-5">true</span>

Note:

Solution: HashTable

Compare the counter of digit string with that of all power of 2s.

e.g. 64 -> {4: 1, 6: 1} == 46 {4:1, 6: 1}

Time complexity: O(1)

Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

bool reorderedPowerOf2(int N) {

auto m = countMap(N);

for (int i = 0; i < 31; ++i)

if (m == countMap(1 << i)) return true;

return false;

}

private:

map<int, int> countMap(int n) {

map<int, int> m;

while (n) {

++m[n % 10];

n /= 10;

}

return m;

}

};

请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.

Buy anything from Amazon to support our website
您可以通过在亚马逊上购物（任意商品）来支持我们

Paypal

Venmo
huahualeetcode

微信打赏