Reordered Power of 2

Difficulty: 🟡 Medium
Tags: Permutations, Math, Bit Manipulation

📜 Problem Statement

You are given an integer n.
You may reorder the digits of n in any way you want (including keeping them in the original order),
but the new number must not start with zero ❌0.

Return true ✅ if and only if you can rearrange the digits so that the result is a power of two ⚡.

📌 Rules & Clarifications

• 🔄 You can rearrange the digits in any order.
• 🚫 No leading zeros are allowed in the result.
• 🧮 A valid result must be equal to 2^k for some integer k ≥ 0.
• 🔍 The function should return true or false.

💡 Examples

Example 1

Input: n = 1
Output: true
Reason: 1 = 2^0 → already a power of two ✅

Example 2

Input: n = 10
Output: false
Reason: Permutations → 10, 01(❌ invalid) → none are powers of two.

🎯 Constraints

• 1 <= n <= 10^9

🛠 Approach / Hints

💡 Key Insight:
Instead of generating all permutations (which can be huge),
compare the digit frequency of n with the digit frequency of all possible powers of two within the given range.

Steps:

1. Generate all powers of two up to 2^30 (since 2^30 = 1073741824 > 10^9).
2. Convert each power of two into a string and count digit occurrences.
3. Count the digits in n.
4. If n’s digit count matches any precomputed power-of-two digit count → return true.
5. Otherwise → return false.

⏳ Complexity

• Precomputation: O(1) → only 30 powers of two.
• Digit counting: O(d) where d ≤ 10.
• Overall: Constant time in practice 🚀.