Problem Description

Given a positive integer n, determine if you can reorder its digits to make a number that is a power of two. You may not use any leading zeros in your reordered number. Return true if such a reordering exists, and false otherwise.

• Each digit of n must be used exactly once.
• Leading zeros are not allowed in the reordered number.
• n is a positive integer (1 ≤ n ≤ 10⁹).
• There is only one input and one output; no need to find all possible orderings, just whether any valid one exists.

Thought Process

The first idea that comes to mind is to generate all possible permutations of the digits of n, check each one, and see if any permutation forms a power of two. However, this is inefficient, especially for numbers with many digits, as the number of permutations grows factorially.

Instead, let's look for a more efficient way. Notice that two numbers are permutations of each other if and only if they have the same digit counts. So, if we precompute all powers of two within the range of n's possible values, and store their digit counts, we can just compare the digit counts of n to each power of two. If any match, we know some permutation of n is a power of two.

This reduces the problem from generating all permutations to a simple comparison of digit frequency maps.

Solution Approach

• Step 1: For all powers of two less than or equal to 10⁹ (since n can be up to 10⁹), compute their digit counts. Store each as a string with sorted digits, or as a frequency map.
• Step 2: For the input n, compute its digit count in the same way (either as a sorted string of digits or as a frequency map).
• Step 3: For each precomputed power of two, check if its digit count matches n's digit count.
• Step 4: If any match is found, return true. Otherwise, return false.

This approach is efficient because there are only about 30 powers of two in the relevant range, so the comparison is quick and avoids unnecessary permutations.

Example Walkthrough

Let's consider n = 128:

• The digits of 128 are 1, 2, 8.
• All powers of two up to 10⁹ include 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, etc.
• Compute the sorted digit string for 128: '128' → '128'.
• Check if any power of two's digits match: 128 is itself a power of two, and its sorted digits are '128'.
• They match, so we return true.

Now, consider n = 124:

• Digits: 1, 2, 4. Sorted: '124'.
• Check powers of two: 124 is not a power of two, and none of the powers of two up to 10⁹ have the sorted digits '124'.
• No match is found, so we return false.

Time and Space Complexity

• Brute-force approach: Generating all permutations of n's digits is O(k!), where k is the number of digits (up to 10). For each permutation, checking if it's a power of two is O(1). This quickly becomes infeasible for larger n.
• Optimized approach: Precomputing all powers of two up to 10⁹ (about 30 numbers), and for each, storing their sorted digit strings (O(1) per number). For the input, sorting its digits is O(k log k), and comparing to each precomputed power of two is O(k) per comparison, for at most 30 comparisons. So, total time complexity is O(k log k + 30k), which is effectively O(1) for practical input sizes.
• Space complexity: Storing up to 30 sorted digit strings, each of length up to 10, so O(1) space.

Summary

The key insight is that instead of generating all digit permutations, we can compare digit counts (or sorted digit strings) between n and all powers of two in the feasible range. This reduces the problem to a set comparison, making the solution both elegant and efficient, and sidestepping the factorial complexity of brute-force permutation generation.

Code Implementation

class Solution:
    def reorderedPowerOf2(self, n: int) -> bool:
        def count_digits(x):
            return ''.join(sorted(str(x)))
        n_count = count_digits(n)
        for i in range(31):  # 2^0 to 2^30 covers all up to 10^9
            if n_count == count_digits(1 << i):
                return True
        return False
      

class Solution {
public:
    bool reorderedPowerOf2(int n) {
        string nCount = countDigits(n);
        for (int i = 0; i < 31; ++i) {
            if (nCount == countDigits(1 << i)) return true;
        }
        return false;
    }
private:
    string countDigits(int x) {
        string s = to_string(x);
        sort(s.begin(), s.end());
        return s;
    }
};
      

class Solution {
    public boolean reorderedPowerOf2(int n) {
        String nCount = countDigits(n);
        for (int i = 0; i < 31; i++) {
            if (nCount.equals(countDigits(1 << i))) {
                return true;
            }
        }
        return false;
    }
    private String countDigits(int x) {
        char[] arr = Integer.toString(x).toCharArray();
        java.util.Arrays.sort(arr);
        return new String(arr);
    }
}
      

var reorderedPowerOf2 = function(n) {
    function countDigits(x) {
        return x.toString().split('').sort().join('');
    }
    let nCount = countDigits(n);
    for (let i = 0; i < 31; i++) {
        if (nCount === countDigits(1 << i)) {
            return true;
        }
    }
    return false;
};