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; } } -
// OJ: https://leetcode.com/problems/reordered-power-of-2/ // Time: O(lg(N)!) // Space: O(lg(N)) class Solution { private: bool isPow2(long long N) { return (N & (N - 1)) == 0; } 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); } }; -
class Solution(object): def reorderedPowerOf2(self, N): """ :type N: int :rtype: bool """ c = collections.Counter(str(N)) return any(c == collections.Counter(str(1 << i)) for i in xrange(32))