Reordered Power of 2: Digit Frequency Matching

Reordered Power of 2 (LeetCode 869) asks: given a positive integer n, can you reorder its digits (without leading zeros) to form a power of 2?

For example, n = 46 returns true because you can rearrange 46 into 64, and 64 is 2^6. But n = 24 returns false because no rearrangement of [2, 4] gives you a power of 2 (42 is not a power of 2 either).

At first glance, this seems like a permutation problem. But there is a much cleaner way to think about it.

Why this problem matters

Reordered Power of 2 is a great example of reducing a seemingly complex problem to a simple lookup. Instead of generating permutations or checking divisibility, you realize that two numbers are rearrangements of each other if and only if they have the same digit frequencies. That insight turns a combinatorial problem into a hash map lookup, and the same idea powers problems like Group Anagrams and Valid Anagram.

The brute force: generate all permutations

The most obvious approach is to generate every permutation of the digits of n and check whether any of them is a power of 2. For a number with d digits, there are d! permutations. A 10-digit number (the maximum for a 32-bit integer) would produce up to 3,628,800 permutations. For each one, you would need to check if it is a power of 2.

That is way too much work. And it completely misses the real structure of the problem.

The key insight: digit frequency matching

Here is the trick. Two numbers are rearrangements of each other if and only if they contain the same digits at the same frequencies. "46" and "64" both have one 4 and one 6. "123" and "321" both have one 1, one 2, and one 3.

So instead of asking "can I rearrange n into some power of 2?", ask: "does any power of 2 have the same digit signature as n?"

The algorithm:

1. Sort the digits of n to get a canonical signature
2. For each power of 2 (up to the maximum possible value), sort its digits too
3. If any sorted form matches, return true
4. If none match, return false

There are only 31 powers of 2 that fit in a 32-bit integer (from 2^0 = 1 to 2^30 = 1073741824). That is a tiny, fixed set to check against.

Step-by-step walkthrough

Let's trace through n = 46. We sort its digits, then compare against the sorted digits of every power of 2 until we find a match or run out of candidates.

The moment we hit 64, the sorted digits match. We return true without checking the remaining powers.

The code

def reorderedPowerOf2(n: int) -> bool:
    target = sorted(str(n))
    return any(sorted(str(1 << i)) == target for i in range(31))

Let's walk through what each piece does:

• sorted(str(n)) converts n to a string, then sorts the characters. For n = 46, this gives ['4', '6']. This is the canonical digit signature.
• 1 << i computes 2^i using a bit shift. This is faster than 2 ** i and avoids importing anything.
• sorted(str(1 << i)) gives the sorted digit signature of each power of 2.
• any(...) short-circuits as soon as it finds a match. If n = 46, it returns true at i = 6 without checking the rest.

Complexity analysis

Since the number of powers of 2 is capped at 31 and the maximum digit count is 10, both time and space are effectively constant. This solution handles any valid input in microseconds.

Building blocks

This problem is built from a few reusable patterns:

Canonical form for comparison

The idea of transforming inputs into a standard form so that equivalent inputs become identical. Sorting the digits of a number is the same technique as sorting the characters of a string to detect anagrams. Any time you need to check if two things are rearrangements of each other, canonicalization is your tool.

Fixed candidate enumeration

Instead of generating candidates from the input (permutations of digits), you enumerate candidates from the answer space (all powers of 2). When the answer space is small and well-defined, this flip in perspective often turns an exponential problem into a linear one.

Short-circuit search

Using any() or an early return to stop as soon as you find what you are looking for. This is a small optimization in this problem, but the pattern matters in problems where the search space is larger.

Edge cases

n = 1: The number 1 is 2^0, so it is already a power of 2. sorted("1") == sorted("1"). Return true.

n = 10: The digits are [1, 0]. No power of 2 has sorted digits ['0', '1']. Return false. Note that leading zeros are not allowed in the reordered number, but you do not need to handle this explicitly. The comparison against actual powers of 2 handles it automatically since no power of 2 has a leading zero.

Large n (e.g., n = 1000000000): This has 10 digits. You only need to check powers of 2 with 10 digits, which are 2^30 = 1073741824. sorted("1000000000") is ['0','0','0','0','0','0','0','0','0','1'] and sorted("1073741824") is ['0','0','1','1','1','2','3','4','7','8']. No match. Return false.

n = 2^k for any k: If n is already a power of 2, it trivially matches itself. The algorithm handles this without special cases.

Common mistakes

Generating permutations instead of using digit signatures. This is the most common mistake. You do not need to generate any permutations. Sorting the digits gives you a canonical form for comparison, reducing the problem from factorial to linear.

Forgetting the range of powers. In a 32-bit context, you need powers from 2^0 through 2^30. If you stop too early, you miss large matches. If you go too far, you waste time (though the overhead is minimal).

Using string equality instead of sorted comparison. Comparing str(n) == str(power) directly checks for exact equality, not rearrangement. You need to sort both sides first.

From understanding to recall

Reordered Power of 2 is a two-step problem once you see the pattern: canonicalize the digits, then check against a fixed set of candidates. But knowing this and recalling it under pressure are different things. The next time you see a problem that says "can you rearrange X to match some target?", you need the canonical form idea to fire immediately.

Spaced repetition makes this automatic. You type the solution from scratch at increasing intervals. After a few cycles, the moment you see "reorder" and "match" in a problem statement, the sorted-digit approach is your first instinct. You spend zero time on the wrong approach and all your time on the details.

Related posts

• Power of Two - The bit manipulation version of checking powers of 2, a useful companion to this digit-based approach
• Group Anagrams - Uses the same sorted-string canonical form to group words by their anagram signature
• Valid Anagram - The simplest version of the frequency counting pattern that powers this problem
• Sort Characters By Frequency - Another problem that uses character frequency analysis as its core technique