LeetCode 869: Reordered Power of 2

Problem Restatement

We are given a positive integer n.

We may reorder its digits in any way.

The reordered number:

1. Cannot have leading zeroes.
2. Must use exactly the same digits.

We need to return True if some reordering forms a power of two.

Otherwise, return False.

Input and Output

Function shape:

class Solution:
    def reorderedPowerOf2(self, n: int) -> bool:
        ...

Examples

Example 1:

n = 1

The number 1 is already a power of two:

2^0 = 1

So the answer is:

True

Example 2:

n = 10

Possible reorderings:

10
01

The second form is invalid because of the leading zero.

10 is not a power of two.

So the answer is:

False

Example 3:

n = 46

Reordering the digits gives:

64

and:

64 = 2^6

So the answer is:

True

First Thought: Try Every Permutation

One direct approach is:

1. Generate every permutation of the digits.
2. Ignore permutations with leading zeroes.
3. Convert each permutation into an integer.
4. Check whether it is a power of two.

This works for small numbers, but the number of permutations grows very quickly.

If there are d digits, there can be up to:

d!

permutations.

We need something simpler.

Key Insight

Two numbers can be reordered into each other exactly when they contain the same digits with the same frequencies.

For example:

So instead of generating permutations, we compare digit frequency signatures.

The plan:

1. Compute the digit signature of n.
2. Generate all powers of two within the valid range.
3. If any power of two has the same digit signature, return True.

Since:

n <= 10^9

we only need powers:

2^0 through 2^30

because:

2^30 = 1073741824

and:

2^31 > 10^9

Algorithm

Define a helper function that returns a digit signature.

One simple signature is the sorted digit string.

For example:

Compute:

target = signature(n)

Then for every power of two:

1. Compute its signature.
2. Compare with target.
3. If equal, return True.

If no match exists, return False.

Correctness

Two integers can be reordered into each other exactly when they contain the same digits with the same frequencies.

The signature function captures this property because sorting the digits produces the same result for all reorderings of the same multiset of digits.

Therefore, n can be reordered into a power of two if and only if some power of two has the same digit signature as n.

The algorithm checks every possible power of two in the valid range, so if such a power exists, the algorithm will find it and return True.

If no matching signature exists, then no digit reordering of n can form a power of two, so returning False is correct.

Complexity

There are only 31 relevant powers of two.

Let:

d = number of digits in n

Since the number of powers is constant, the runtime is effectively constant.

Implementation

class Solution:
    def reorderedPowerOf2(self, n: int) -> bool:
        def signature(x: int) -> str:
            return "".join(sorted(str(x)))

        target = signature(n)

        for power in range(31):
            candidate = 1 << power

            if signature(candidate) == target:
                return True

        return False

Code Explanation

The helper function creates a digit signature:

def signature(x: int) -> str:
    return "".join(sorted(str(x)))

For example:

Next:

target = signature(n)

stores the signature of the input.

Then we generate powers of two:

for power in range(31):

The expression:

1 << power

computes:

2^power

For each candidate power of two:

candidate = 1 << power

we compare signatures:

if signature(candidate) == target:
    return True

If no match is found after checking all powers:

return False

Testing

def test_reordered_power_of_2():
    s = Solution()

    assert s.reorderedPowerOf2(1) is True
    assert s.reorderedPowerOf2(10) is False
    assert s.reorderedPowerOf2(16) is True
    assert s.reorderedPowerOf2(24) is False
    assert s.reorderedPowerOf2(46) is True
    assert s.reorderedPowerOf2(218) is True
    assert s.reorderedPowerOf2(125) is True

    print("all tests passed")

test_reordered_power_of_2()

Test meaning: