Description
You are given an 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 so that the resulting number is a power of two.
Example 1:
Input: n = 1
Output: true
Example 2:
Input: n = 10
Output: false
Constraints:
Solutions
Solution 1: Enumeration
We can enumerate all powers of 2 in the range [1, 109] and check if their digit composition is the same as the given number.
Define a function f(x) that represents the digit composition of number x. We can convert the number x into an array of length 10, or a string sorted by digit size.
First, we calculate the digit composition of the given number n as target = f(n). Then, we enumerate i starting from 1, shifting i left by one bit each time (equivalent to multiplying by 2), until i exceeds 109. For each i, we calculate its digit composition and compare it with target. If they are the same, we return true; if the enumeration ends without finding the same digit composition, we return false.
Time complexity O(log^2 M), space complexity O(log M). Where M is the upper limit of the input range {10}9 for this problem.
PythonJavaC++GoTypeScriptRust
class Solution:
def reorderedPowerOf2(self, n: int) -> bool:
def f(x: int) -> List[int]:
cnt = [0] * 10
while x:
x, v = divmod(x, 10)
cnt[v] += 1
return cnt
target = f(n)
i = 1
while i <= 10**9:
if f(i) == target:
return True
i <<= 1
return False(code-box)
class Solution {
public boolean reorderedPowerOf2(int n) {
String target = f(n);
for (int i = 1; i <= 1000000000; i <<= 1) {
if (target.equals(f(i))) {
return true;
}
}
return false;
}
private String f(int x) {
char[] cnt = new char[10];
for (; x > 0; x /= 10) {
cnt[x % 10]++;
}
return new String(cnt);
}
}(code-box)
class Solution {
public:
bool reorderedPowerOf2(int n) {
string target = f(n);
for (int i = 1; i <= 1000000000; i <<= 1) {
if (target == f(i)) {
return true;
}
}
return false;
}
private:
string f(int x) {
char cnt[10] = {};
while (x > 0) {
cnt[x % 10]++;
x /= 10;
}
return string(cnt, cnt + 10);
}
};(code-box)
func reorderedPowerOf2(n int) bool {
target := f(n)
for i := 1; i <= 1000000000; i <<= 1 {
if bytes.Equal(target, f(i)) {
return true
}
}
return false
}
func f(x int) []byte {
cnt := make([]byte, 10)
for x > 0 {
cnt[x%10]++
x /= 10
}
return cnt
}(code-box)
function reorderedPowerOf2(n: number): boolean {
const f = (x: number) => {
const cnt = Array(10).fill(0);
while (x > 0) {
cnt[x % 10]++;
x = (x / 10) | 0;
}
return cnt.join(',');
};
const target = f(n);
for (let i = 1; i <= 1_000_000_000; i <<= 1) {
if (target === f(i)) {
return true;
}
}
return false;
}(code-box)
impl Solution {
pub fn reordered_power_of2(n: i32) -> bool {
fn f(mut x: i32) -> [u8; 10] {
let mut cnt = [0u8; 10];
while x > 0 {
cnt[(x % 10) as usize] += 1;
x /= 10;
}
cnt
}
let target = f(n);
let mut i = 1i32;
while i <= 1_000_000_000 {
if target == f(i) {
return true;
}
i <<= 1;
}
false
}
}(code-box)
