Problem
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.
Examples
Example 1:
|
|
Example 2:
|
|
Constraints
1 <= n <= 109
Solution
Method 1 - Generate Powers of Two and Compare Anagrams
We know power of 2:
|
|
Consider the input number 46. The answer should be true because 64 is a power of 2. Generating all permutations of 46 is time-consuming.
Instead, we can generate and sort the digits of powers of 2, for example, 64 remains 64, and 1024 becomes 4210 when sorted. When given an input number like 46, we can sort its digits to get 64, which matches a power of 2.
To generate powers of 2, we can use the left shift operator, continuing until the value exceeds the constraint of 10^9.
This problem in a way is similar to Group Anagrams.
Code
|
|
Complexity
- Time:
O(m log m)
, wherem
is number of digits- Transform method takes
O(m)
- And we call transform method
log m
time
- Transform method takes
- Space:
O(m)
Method 2 - Generate Power of Twos and Compare Digits
Code
|
|
Complexity
- ⏰ Time complexity:
O(m log m)
, where m is the number of digits in n.- For each of the 31 possible powers of 2 (since
2³⁰ > 10⁹
), you convert the number to a string (O(m)
), sort its digits (O(m log m)
), and compare arrays (O(m)
). - So, total time is O(
31 × m log m
) =O(m log m).
- For each of the 31 possible powers of 2 (since
- 🧺 Space complexity:
O(m)
- Each call to
sortedDigits
creates a char array of length m. - No extra space grows with input beyond this temporary array.
- Each call to
Method 3 - Generate Power of Twos and Compare Digit Frequency
Code
|
|
Complexity
- Time:
O(m)
. O(31 × m), where m is the number of digits in N.- For each of the 31 possible powers of 2 (since 2³⁰ > 10⁹), you compute the digit frequency (O(m)) and compare arrays (O(1), since arrays are of fixed size 10).
- So, total time is O(31 × m) = O(m).
- Space:
O(1)