Reordered Power of 2 — Medium Problem & Solution

Problem statement

You may reorder the digits of n in any way, as long as the result has no leading zero.

Return true if some reordering is a power of two.

Example 1

Input: n = 16
Output: true
Explanation: 16 is already 2⁴.

Example 2

Input: n = 46
Output: true
Explanation: Reordering to 64 gives 2⁶.

Example 3

Input: n = 10
Output: false
Explanation: The only reorderings are 10 and 01, and neither is a power of two.

Constraints

• 1 <= n <= 1000000000

How to solve Reordered Power of 2

Flip the search around. Instead of generating permutations of n, generate the handful of powers of two in range and test whether any shares n's digit multiset.

Approach

1. Write a helper that turns a number into a 10-slot digit-count signature.
2. Compute the signature of n.
3. Walk p = 1, 2, 4, … while p stays within the input bound, comparing signatures.
4. Return true on the first match.

Why it works

Two numbers are permutations of one another precisely when their digit counts agree — and the leading-zero rule is automatic, because a power of two never starts with 0 and the signature comparison already forces equal digit counts.

Complexity

• Time — O(30 · log n)
• Space — O(1)

Pitfalls

• Generating all permutations is up to 10! and needlessly slow.
• Sorting the digit strings also works, but the counts version avoids a string sort per candidate.
• The loop bound must cover 2^30, which exceeds the input ceiling — stop once the power passes it.

Reference solution

Python

def reorderedPowerOf2(n: int) -> bool:
    def sig(v: int):
        count = [0] * 10
        while v > 0:
            count[v % 10] += 1
            v //= 10
        return tuple(count)

    want = sig(n)
    p = 1
    while p <= 1000000000:
        if sig(p) == want:
            return True
        p *= 2
    return False

JavaScript

var reorderedPowerOf2 = function(n) {
    var sig = function(v) {
        var count = [];
        for (var t = 0; t < 10; t++) count.push(0);
        while (v > 0) {
            count[v % 10]++;
            v = Math.floor(v / 10);
        }
        return count.join(",");
    };
    var want = sig(n);
    for (var p = 1; p <= 1000000000; p *= 2) {
        if (sig(p) === want) return true;
    }
    return false;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More math problems

• Find the Winner of the Circular Game Medium
• Stone Game VII Medium
• Number of Ways to Divide a Long Corridor Medium
• Count Ways to Group Overlapping Ranges Medium
• Count Number of Ways to Place Houses Medium
• Count Number of Texts Medium