Formatted question description: https://leetcode.ca/all/869.html
869. Reordered Power of 2 (Medium)
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:
Input: 46
Output: true
Note:
1 <= N <= 10^9
Solution 1. Permutations
Traverse all the permutations of N, and examine each of them whether it is power of 2.
// OJ: https://leetcode.com/problems/reordered-power-of-2/
// Time: O(lg(N)! * log(N)),
// where lg(N) is number of digits in N base-10,
// and log(N) is number of digits in N base-2.
// O(lg(N)!) is because of permutation, log(N) is because of testing `isPow2`.
// Space: O(lg(N))
class Solution {
private:
bool isPow2(long long N) {
while (N != 1) {
if (N % 2) return false;
N /= 2;
}
return true;
}
string num;
bool dfs(int start) {
if (start == num.size()) return isPow2(stoll(num));
for (int i = start; i < num.size(); ++i) {
if (num[i] == '0' && start == 0) continue;
swap(num[start], num[i]);
if (dfs(start + 1)) return true;
swap(num[start], num[i]);
while (i + 1 < num.size() && num[i] == num[i + 1]) ++i;
}
return false;
}
public:
bool reorderedPowerOf2(int N) {
while (N) {
num.push_back('0' + (N % 10));
N /= 10;
}
sort(num.begin(), num.end(), greater<char>());
return dfs(0);
}
};
Solution 2. Counting
There are only 32 possible powers of 2. Count the digits of N and compare the counts with those of a power of 2.
// OJ: https://leetcode.com/problems/reordered-power-of-2/
// Time: O(lg(N))
// where lg(N) is number of digits in N base-10.
// There are just 32 possible powers of 2. The comparison is O(lg(N)).
// Space: O(lg(N))
class Solution {
private:
vector<int> count(int N) {
vector<int> cnt(10, 0);
while (N) {
cnt[N % 10]++;
N /= 10;
}
return cnt;
}
public:
bool reorderedPowerOf2(int N) {
auto cnt = count(N);
for (int i = 0; i < 31; ++i) {
auto c = count(1 << i);
if (equal(cnt.begin(), cnt.end(), c.begin())) return true;
}
return false;
}
};
Java
class Solution {
public boolean reorderedPowerOf2(int N) {
if (N == 1000000000)
return false;
if (N < 10)
return N == 1 || N == 2 || N == 4 || N == 8;
int length = String.valueOf(N).length();
int lower = (int) Math.pow(10, length - 1);
int upper = lower * 10;
int log = (int) (Math.log(lower) / Math.log(2));
int power2 = (int) Math.pow(2, log);
while (power2 < lower)
power2 *= 2;
int[] numCount = new int[10];
char[] array = String.valueOf(N).toCharArray();
for (char c : array)
numCount[c - '0']++;
while (power2 < upper) {
if (check(power2, numCount))
return true;
power2 *= 2;
}
return false;
}
public boolean check(int power2, int[] numCount) {
int[] count = new int[10];
char[] array = String.valueOf(power2).toCharArray();
for (char c : array)
count[c - '0']++;
for (int i = 0; i <= 9; i++) {
if (count[i] != numCount[i])
return false;
}
return true;
}
}