Problem Description

You are given an integer n. Your task is to determine whether you can rearrange the digits of n (in any order, including keeping the original order) to form a number that is a power of 2.

The only constraint is that the rearranged number cannot have leading zeros (the first digit cannot be 0).

Return true if it's possible to rearrange the digits to form a power of 2, otherwise return false.

For example:

• If n = 46, you can rearrange it to 64, which is 2^6, so return true
• If n = 1, it's already 2^0, so return true
• If n = 10, no valid rearrangement forms a power of 2, so return false

The solution works by comparing the digit composition (frequency of each digit) of the given number with all powers of 2 within the valid range. The function f(x) counts how many times each digit (0-9) appears in number x and returns this as an array. The algorithm then checks all powers of 2 from 1 to 10^9 to see if any of them have the same digit composition as the input number n. If a match is found, it means we can rearrange n to form that power of 2.

Intuition

The key insight is that if we can rearrange the digits of n to form a power of 2, then n and that power of 2 must have exactly the same digits - just in different orders. For example, 46 and 64 both contain one '4' and one '6'.

This means we don't actually need to try all possible permutations of n's digits (which could be factorial time complexity). Instead, we can flip the problem around: check if n has the same digit composition as any power of 2.

Since rearranging digits doesn't change which digits we have or how many of each, we can simply count the frequency of each digit (0-9) in our number n. If these frequencies match exactly with the frequencies of any power of 2, then we know we can rearrange n to form that power of 2.

The bounds are important here. The input n can be at most 10^9, which means any valid rearrangement will also be at most 10^9. Powers of 2 grow exponentially (2^30 is already over 10^9), so we only need to check about 30 powers of 2.

This transforms what could be a complex permutation problem into a simple comparison problem: generate all powers of 2 up to 10^9, and for each one, check if it has the same digit frequency distribution as n. If we find a match, return true. If we check all powers of 2 without finding a match, return false.

Learn more about Math and Sorting patterns.

Solution Approach

The implementation uses a helper function f(x) to capture the digit composition of any number x. This function creates an array cnt of size 10 where cnt[i] represents how many times digit i appears in x.

The function f(x) works by repeatedly extracting the last digit of x using the divmod operation:

• x, v = divmod(x, 10) simultaneously divides x by 10 (removing the last digit) and gets the remainder v (the last digit)
• We increment cnt[v] to count this digit
• This continues until x becomes 0

Once we have this helper function, the main algorithm follows these steps:

1. Calculate target composition: First, we compute target = f(n), which gives us the digit frequency array for the input number n.

2. Enumerate powers of 2: We start with i = 1 (which is 2^0) and keep doubling it using the left shift operation i <<= 1 (equivalent to multiplying by 2).

3. Check each power of 2: For each power of 2, we calculate its digit composition using f(i) and compare it with target. If they match exactly (same frequencies for all digits 0-9), we've found a power of 2 that can be formed by rearranging n's digits.

4. Boundary condition: We continue checking until i exceeds 10^9, since any rearrangement of n cannot exceed this value.

5. Return result: If we find a match, return True immediately. If we've checked all powers of 2 up to 10^9 without finding a match, return False.

The time complexity is O(log n * log max_value) where we check about 30 powers of 2, and for each one, we extract its digits (at most 10 digits). The space complexity is O(1) since we only use fixed-size arrays of length 10.

Example Walkthrough

Let's walk through the example where n = 46.

Step 1: Calculate the digit composition of n = 46

• Using function f(46):
  • 46 % 10 = 6, so cnt[6] = 1, then 46 // 10 = 4
  • 4 % 10 = 4, so cnt[4] = 1, then 4 // 10 = 0
  • Result: target = [0,0,0,0,1,0,1,0,0,0] (one '4' and one '6')

Step 2: Check powers of 2

• Start with i = 1 (2^0):

  • f(1) = [0,1,0,0,0,0,0,0,0,0] (one '1')
  • Doesn't match target ❌

• i = 2 (2^1):

  • f(2) = [0,0,1,0,0,0,0,0,0,0] (one '2')
  • Doesn't match target ❌

• i = 4 (2^2):

  • f(4) = [0,0,0,0,1,0,0,0,0,0] (one '4')
  • Doesn't match target ❌

• Continue through i = 8, 16, 32...

• i = 64 (2^6):

  • f(64) = [0,0,0,0,1,0,1,0,0,0] (one '4' and one '6')
  • Matches target! ✓

Step 3: Return true

Since we found that 64 has the same digit composition as 46, we know we can rearrange the digits of 46 to form 64, which is a power of 2.

The algorithm efficiently checked only the powers of 2 rather than trying all possible permutations of 46 (which would be 46 and 64 in this case). This demonstrates how the solution transforms a permutation problem into a simple frequency comparison problem.

Solution Implementation

Time and Space Complexity

Time Complexity: O(log^2 M), where M = 10^9 is the upper limit of the input range.

The analysis breaks down as follows:

• The outer loop iterates through all powers of 2 up to 10^9. Since we're doubling i each time (i <<= 1), we have log₂(10^9) ≈ 30 iterations.
• For each iteration, we call function f(i) which extracts digits from the number. The f function runs in O(log₁₀(i)) time, as it processes each digit of the number. The maximum value of i is 10^9, so this takes at most O(log₁₀(10^9)) = O(9) = O(log M) time.
• We also call f(n) once at the beginning, which takes O(log n) = O(log M) time.
• The comparison f(i) == target takes O(10) = O(1) time since we're comparing two arrays of fixed size 10.

Therefore, the total time complexity is O(log M) + O(log M × log M) = O(log^2 M).

Space Complexity: O(log M)

The space analysis:

• Function f creates an array cnt of fixed size 10, which is O(1).
• The target array stores the digit count of n, also using O(1) space.
• The recursive call stack depth is at most 1 since f is not recursive.
• However, when considering the representation of numbers themselves and the digit extraction process, we need O(log M) space to represent the largest possible number in the range.

Therefore, the space complexity is O(log M).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Upper Bound for Powers of 2

A common mistake is using the wrong upper bound when checking powers of 2. Some might incorrectly assume the upper bound should be based on the maximum value that can be formed from rearranging the digits of n.

Pitfall Example:

# INCORRECT: Using n's digit count to determine upper bound
max_possible = 10 ** len(str(n)) - 1
power_of_two = 1
while power_of_two <= max_possible:
    # Check power of 2
    power_of_two <<= 1

Why it's wrong: If n = 128, the maximum rearrangement is 821, but we'd miss checking 1024 (2^10) which has the same digits as 1024 → {0:1, 1:1, 2:1, 4:1}. The digit composition matters, not just the original number's magnitude.

Solution: Always use 10^9 as the upper bound since the problem constraints specify this limit, ensuring all valid powers of 2 are checked regardless of the input's digit count.

2. String-Based Comparison Instead of Frequency Arrays

Some might try to sort the digits as strings and compare them directly:

Pitfall Example:

# INCORRECT: String sorting approach
def reorderedPowerOf2(self, n: int) -> bool:
    sorted_n = sorted(str(n))
    power_of_two = 1
    while power_of_two <= 10**9:
        if sorted(str(power_of_two)) == sorted_n:
            return True
        power_of_two <<= 1
    return False

Why it's problematic: While this works functionally, it's less efficient due to string conversions and sorting operations (O(d log d) for each comparison where d is the number of digits). The frequency array approach is O(d) for both creation and comparison.

3. Off-by-One Error in Power Generation

Starting with the wrong initial power or using incorrect increment logic:

Pitfall Example:

# INCORRECT: Starting from 2 instead of 1
power_of_two = 2  # Misses 2^0 = 1
while power_of_two <= 10**9:
    # Check logic
    power_of_two *= 2

Solution: Always start with power_of_two = 1 (which is 2^0) to ensure all powers are checked.

4. Forgetting Edge Cases

Not handling single-digit inputs properly, especially n = 1, 2, 4, 8:

Pitfall Example:

# INCORRECT: Premature optimization that breaks edge cases
if n < 10:
    # Assuming single digits can't be rearranged
    return n in [1, 2, 4, 8]  # But what about checking if it's already a power of 2?

Solution: The frequency-based approach naturally handles all cases uniformly without special-casing single digits.