The goal is to determine whether the digits of a given integer n can be reordered to form a power of two. The reordering must not produce a number with a leading zero.

For example:

• n = 1 → valid (1 is 2⁰)
• n = 10 → not valid (digits 1 and 0 cannot form a power of two without leading zeros)

You are allowed to permute the digits freely, but cannot add, remove, or change digits.

Intuition

The key observation is that the digits of powers of two have specific digit combinations. If we can check whether n can be rearranged to match the digits of any power of two up to 2³⁰ (since 2³⁰ is slightly over 10⁹), then we can decide whether it's valid.

Instead of generating all permutations of n, we use a digit frequency encoding. The idea is that two numbers are permutations of each other if and only if they have the same count of each digit.

We create a unique representation of digit counts using powers of 10:

• For example, the number 128 results in count = 10^1 + 10^2 + 10^8

We precompute the digit count encodings for all powers of two from 2⁰ to 2²⁹ and compare them to the encoding of n.

Approach

We define a helper function counter(n) that returns an encoded integer representing the digit frequencies of n. Then we check if counter(n) matches any of the encodings for powers of two.

C++ Code

class Solution {
 public:
  bool reorderedPowerOf2(int n) {
    int count = counter(n);

    for (int i = 0; i < 30; ++i)
      if (counter(1 << i) == count)
        return true;

    return false;
  }

 private:
  int counter(int n) {
    int count = 0;

    for (; n > 0; n /= 10)
      count += pow(10, n % 10);

    return count;
  }
};

• The counter() function compresses the digit frequency into a single integer.
• We loop through all powers of two from 2⁰ to 2²⁹ and check if any have the same digit encoding as n.

JavaScript Version

var reorderedPowerOf2 = function(n) {
    const counter = (num) => {
        let count = Array(10).fill(0);
        for (const digit of String(num)) {
            count[Number(digit)]++;
        }
        return count.join('');
    };

    const target = counter(n);
    for (let i = 0; i < 30; i++) {
        if (counter(1 << i) === target) {
            return true;
        }
    }
    return false;
};

Here, we use a stringified frequency array as a unique key.

Python Version

class Solution:
    def reorderedPowerOf2(self, n: int) -> bool:
        def counter(x):
            count = [0] * 10
            while x:
                count[x % 10] += 1
                x //= 10
            return tuple(count)

        target = counter(n)
        for i in range(30):
            if counter(1 << i) == target:
                return True
        return False

We use a tuple of digit frequencies for compact comparison.

Time and Space Complexity

Time Complexity:

• O(1) in practice, since we check only 30 powers of two.
• Each counter() call processes at most 10 digits → O(1).

Space Complexity:

• O(1) for digit frequency storage.

Final Thoughts

This problem is about pattern matching, not permutation generation. Using a compact digit frequency encoding avoids the overhead of generating all digit permutations. By comparing against all valid power-of-two patterns, we can reach a decision efficiently.