#869

Medium

LeetCode Problem Workspace

Reordered Power of 2

Determine if a number's digits can be rearranged to form a power of two using counting and hash-based checks.

hash table math sorting counting enumeration

Problem Statement

Given an integer n, reorder its digits in any possible arrangement such that no number begins with zero. Return true if the reordered number can be a power of two.

For example, n = 1 returns true since 1 itself is a power of two, while n = 10 returns false because no rearrangement forms a power of two. Implement a solution that efficiently checks possible digit combinations without generating all permutations.

Examples

Example 1

Input: n = 1

Output: true

Example details omitted.

Example 2

Input: n = 10

Output: false

Example details omitted.

Constraints

1 <= n <= 109

Solution Approach

Digit Counting with Hash

Convert n to a string and create a frequency map of its digits. For all powers of two within range, precompute their digit counts and store them in a hash set for O(1) comparison.

Compare Patterns Efficiently

Instead of generating all permutations of n, compare the digit count map of n with precomputed digit count maps of powers of two. If a match exists, return true.

Optimization by Range

Only consider powers of two that have the same number of digits as n to reduce unnecessary checks. This avoids mismatches caused by differing lengths and ensures faster execution.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on the number of powers of two up to 10^9 and comparing digit counts, roughly O(log n). Space complexity is O(log n) for storing precomputed hash sets of digit counts.

What Interviewers Usually Probe

Ask if brute-force permutations are required or if a counting method is possible.
Check if candidate optimizations use digit frequency maps rather than full sorting or permutation generation.
Probe understanding of why hashing digit counts improves performance over naive checking.

Common Pitfalls or Variants

Common pitfalls

Failing to precompute powers of two and checking all permutations leads to timeouts.
Ignoring leading zero constraints results in incorrect matches.
Not comparing digit counts properly can cause false negatives even if a valid rearrangement exists.

Follow-up variants

Determine if digits can form any perfect square instead of a power of two.
Return all powers of two that can be formed by rearranging the digits of n.
Check the same property for numbers with a fixed number of digits rather than the input's length.

FAQ

What is the main idea behind Reordered Power of 2?

The key is to use a digit frequency hash to check if a number's digits can match a precomputed power of two, avoiding permutations.

Why is hashing digit counts faster than generating permutations?

Because comparing frequency maps avoids factorial time complexity, reducing checks to O(log n) with precomputed powers.

Does Reordered Power of 2 allow numbers with leading zeros?

No, any rearranged number must have a non-zero leading digit to be considered valid.

How many powers of two need to be precomputed?

All powers of two with digit lengths up to the number of digits in n, which is roughly up to 2^30 for n <= 10^9.

Can GhostInterview handle different patterns like Hash Table plus Math?

Yes, it specifically guides the candidate to apply counting, hashing, and mathematical checks tailored to this problem's pattern.

terminal

Solution

Solution 1: Enumeration

We can enumerate all powers of 2 in the range $[1, 10^9]$ and check if their digit composition is the same as the given number.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def reorderedPowerOf2(self, n: int) -> bool:
        def f(x: int) -> List[int]:
            cnt = [0] * 10
            while x:
                x, v = divmod(x, 10)
                cnt[v] += 1
            return cnt

        target = f(n)
        i = 1
        while i <= 10**9:
            if f(i) == target:
                return True
            i <<= 1
        return False

Continue Practicing

#914 x of a kind in a deck of cards #923 3sum with multiplicity #939 minimum area rectangle