Reordered Power of 2

Problem 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.

Key Insights

• A power of two has a unique binary representation, which can be derived from the number of digits and their counts.
• We can check if a number can be rearranged to form a power of two by comparing the digit counts of n with the digit counts of all powers of two within the range of n.
• The maximum power of two that we need to consider is 2^30, since 2^30 is 1073741824, which exceeds the upper limit of n (10^9).

Space and Time Complexity

Time Complexity: O(1) - The number of powers of two we check is constant (up to 31). Space Complexity: O(1) - We use a fixed-size array to count digits.

Solution

To determine if the digits of the integer n can be rearranged to form a power of two, we can follow these steps:

1. Precompute the digit counts for all powers of two from 2^0 to 2^30.
2. Count the digits of the input number n.
3. Compare the digit count of n with each precomputed power of two's digit count.
4. If there is a match, return true; otherwise, return false.

Code Solutions