LeetCode 869 - Reordered Power of 2

The problem gives us a positive integer n and asks whether its digits can be rearranged to form a power of two. The rearrangement may keep the digits in their original order or place them in any other order, but the resulting number cannot contain a leading zero.

leetcodemediumhash-tablemathsortingcountingenumeration

LeetCode Problem 869

Difficulty: 🟡 Medium
Topics: Hash Table, Math, Sorting, Counting, Enumeration

Solution

Problem Understanding

The problem gives us a positive integer n and asks whether its digits can be rearranged to form a power of two. The rearrangement may keep the digits in their original order or place them in any other order, but the resulting number cannot contain a leading zero.

A power of two is any number of the form:

$2^k$

for some non-negative integer k.

For example, if n = 128, we can rearrange its digits into 128, which is already a power of two, so the answer is true. If n = 821, we can rearrange the digits into 128, so the answer is also true. However, if no permutation of the digits forms a power of two, the answer is false.

The important detail is that we are not allowed to introduce or remove digits. Every digit must appear exactly the same number of times in the reordered number. This means the problem is fundamentally about comparing digit frequency distributions.

The constraints are relatively small:

$1 \leq n \leq 10^9$

Since 10^9 is not extremely large, there are only a limited number of powers of two we need to consider. The largest relevant power of two is:

$2^{30} = 1073741824$

because 2^30 is slightly larger than 10^9, and all smaller powers cover every possible digit length we need.

Several edge cases are important:

  • Numbers containing zeros can be tricky because leading zeros are not allowed.
  • Numbers with repeated digits require exact frequency matching.
  • Single-digit inputs such as 1, 2, 4, and 8 should immediately return true.
  • Numbers that are already powers of two should still work without special handling.
  • Very large values near 10^9 must still be processed efficiently.

Approaches

Brute Force Approach

A naive solution would generate every possible permutation of the digits of n, convert each permutation into an integer, reject permutations with leading zeros, and check whether the resulting number is a power of two.

This approach is correct because it exhaustively tests every valid digit arrangement. If any arrangement forms a power of two, we return true; otherwise, we return false.

However, this method becomes impractical very quickly. If the number contains d digits, there can be up to:

$d!$

different permutations.

Even though the constraint only goes up to 10 digits, factorial growth is extremely expensive. Repeated digits reduce the number of unique permutations somewhat, but the worst-case runtime is still far too large for an efficient solution.

Optimal Approach

The key observation is that two numbers can be rearranged into each other if and only if they contain exactly the same digits with the same frequencies.

For example:

  • 128 and 821 both contain one 1, one 2, and one 8
  • 1024 and 2041 both contain one 0, one 1, one 2, and one 4

Instead of generating permutations, we can compute a canonical representation of the digits. The easiest choice is sorting the digits.

If two numbers have the same sorted digit string, then one can be rearranged into the other.

We precompute all powers of two within the valid range, sort their digits, and store these signatures in a hash set. Then we sort the digits of n and check whether its signature exists in the set.

This avoids permutation generation entirely and reduces the problem to fast lookup operations.

Approach Time Complexity Space Complexity Notes
Brute Force O(d! × d) O(d!) Generates every permutation and checks each one
Optimal O(30 × d log d) O(30) Compares sorted digit signatures of powers of two

Here, d is the number of digits in n, and the constant 30 comes from the number of relevant powers of two.

Algorithm Walkthrough

  1. Convert the input number n into a canonical digit representation.

We need a way to uniquely identify the digit composition of a number. Sorting the digits works perfectly because any permutation of the same digits produces the same sorted string.

For example:

  • 821 → "128"
  • 128 → "128"

Since both signatures match, the numbers are rearrangements of each other. 2. Generate every relevant power of two.

Since:

$2^{30} > 10^9$

we only need to examine powers:

$2^0, 2^1, \dots, 2^{30}$

This is a very small finite set. 3. Compute the sorted digit signature for each power of two.

For every power:

  • Convert it to a string
  • Sort the digits
  • Store the resulting signature in a hash set

A hash set is chosen because membership checks are extremely fast, averaging constant time. 4. Compute the signature of n.

We apply the exact same transformation to n:

  • Convert to string
  • Sort digits
  • Join into a canonical representation
  1. Check whether the signature exists in the set.

If the signature is present, then some power of two has exactly the same digit frequencies as n, meaning the digits can be reordered to form that power of two.

Otherwise, no valid rearrangement exists.

Why it works

The algorithm relies on a fundamental property of permutations: two numbers are permutations of each other if and only if their digit frequency counts are identical.

Sorting digits creates a canonical representation for every permutation class. Every rearrangement of the same digits produces the same sorted sequence, and different digit compositions produce different sequences.

Therefore, if the sorted digits of n match the sorted digits of some power of two, then n can be reordered into that power of two. Conversely, if no match exists, then no valid rearrangement can produce a power of two.

Python Solution

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

        power_signatures = set()

        for exponent in range(31):
            power_of_two = 1 << exponent
            power_signatures.add(signature(power_of_two))

        return signature(n) in power_signatures

The implementation begins by defining a helper function called signature. This function converts a number into its canonical digit representation by sorting its digits and joining them back into a string.

For example:

  • 821 becomes "128"
  • 1024 becomes "0124"

Next, we create a hash set called power_signatures. This set stores the digit signatures of all powers of two within the valid range.

The loop iterates through exponents from 0 to 30. Using bit shifting:

1 << exponent

efficiently computes:

$2^{\text{exponent}}$

Each power's signature is added to the set.

Finally, we compute the signature of n and check whether it exists in the set. Since set membership is very fast, the overall solution is highly efficient.

Go Solution

package main

import (
	"sort"
	"strconv"
)

func reorderedPowerOf2(n int) bool {
	signature := func(value int) string {
		digits := []byte(strconv.Itoa(value))

		sort.Slice(digits, func(i, j int) bool {
			return digits[i] < digits[j]
		})

		return string(digits)
	}

	powerSignatures := make(map[string]bool)

	for exponent := 0; exponent <= 30; exponent++ {
		powerOfTwo := 1 << exponent
		powerSignatures[signature(powerOfTwo)] = true
	}

	return powerSignatures[signature(n)]
}

The Go implementation follows the same overall strategy as the Python version, but there are a few language-specific differences.

Go does not have a built-in sorted string function, so we convert the string into a byte slice and use sort.Slice to sort the digits manually.

Instead of a Python set, we use:

map[string]bool

to simulate hash set behavior.

Bit shifting works the same way as in Python and efficiently generates powers of two.

Since the largest relevant power is 2^30, integer overflow is not an issue in Go's standard integer range.

Worked Examples

Example 1

Input:

n = 1

First, compute the signature of 1.

Value Sorted Digits
1 "1"

Now generate powers of two:

Power of Two Signature
1 "1"
2 "2"
4 "4"
8 "8"

The signature "1" exists in the set, so the answer is:

true

Example 2

Input:

n = 10

Compute the signature:

Value Sorted Digits
10 "01"

Now compare against power-of-two signatures:

Power of Two Signature
1 "1"
2 "2"
4 "4"
8 "8"
16 "16"
32 "23"
64 "46"

No power of two has signature "01".

Therefore:

false

Additional Example

Input:

n = 821

Compute the signature:

Value Sorted Digits
821 "128"

Now examine powers of two:

Power of Two Signature
128 "128"

A match exists, so:

true

Complexity Analysis

Measure Complexity Explanation
Time O(30 × d log d) We sort at most 31 numbers, each with d digits
Space O(30) The hash set stores signatures for at most 31 powers of two

The number of powers of two we examine is fixed and very small, so the runtime is effectively constant in practice.

The dominant operation is sorting the digits of each number. Since a number up to 10^9 has at most 10 digits, even the sorting cost is tiny.

The space usage is also effectively constant because the hash set never stores more than 31 entries.

Test Cases

solution = Solution()

assert solution.reorderedPowerOf2(1) == True       # smallest power of two
assert solution.reorderedPowerOf2(10) == False     # leading zero would be required
assert solution.reorderedPowerOf2(16) == True      # already a power of two
assert solution.reorderedPowerOf2(61) == True      # can reorder into 16
assert solution.reorderedPowerOf2(821) == True     # can reorder into 128
assert solution.reorderedPowerOf2(218) == True     # another permutation of 128
assert solution.reorderedPowerOf2(24) == False     # cannot form any power of two
assert solution.reorderedPowerOf2(46) == True      # can reorder into 64
assert solution.reorderedPowerOf2(100) == False    # repeated zeros prevent valid power
assert solution.reorderedPowerOf2(1024) == True    # larger valid power of two
assert solution.reorderedPowerOf2(2048) == True    # already a power of two
assert solution.reorderedPowerOf2(625) == False    # no matching digit signature
assert solution.reorderedPowerOf2(1073741824) == True  # 2^30
Test Why
1 Smallest valid input
10 Tests leading-zero restriction
16 Already a power of two
61 Requires digit reordering
821 Multi-digit permutation case
218 Another valid permutation
24 Similar digits but invalid
46 Valid two-digit rearrangement
100 Repeated zero edge case
1024 Larger valid power
2048 Existing power of two
625 No possible rearrangement
1073741824 Largest relevant power of two

Edge Cases

One important edge case involves numbers containing zeros, such as 10 or 100. A naive permutation-based implementation might accidentally allow leading zeros and incorrectly treat "01" as 1. The problem explicitly forbids leading zeros, so 10 cannot become 1. Our implementation avoids this issue naturally because sorted digit signatures must match exactly, including all zeros.

Another tricky case is repeated digits. For example, 222 cannot form any power of two even though powers of two may contain the digit 2. The exact frequency counts must match. By sorting all digits, our algorithm guarantees that duplicate counts are preserved correctly.

Single-digit inputs are also important. Values such as 1, 2, 4, and 8 should return true, while values like 3, 5, and 7 should return false. Since our method compares digit signatures directly against all powers of two, these cases are handled automatically without requiring special branching logic.

Large boundary values near 10^9 are another possible source of bugs. Some implementations may not generate enough powers of two and accidentally miss valid matches. By checking all exponents from 0 through 30, we guarantee complete coverage for the entire constraint range.