Reordered Power of 2 - Solution & Explanation
Problem Statement
You are given an integer n. We reorder the digits in any order (including the original order) such that the leading digit is not zero.
Return true if and only if we can do this so that the resulting number is a power of two.
Example 1:
Input: n = 1 Output: true
Example 2:
Input: n = 10 Output: false
Constraints:
1 <= n <= 109
Approach Overview
Problem Overview: Given an integer n, determine whether you can reorder its digits so the resulting number becomes a power of two. The reordered number cannot have leading zeros. The core challenge is verifying whether any permutation of the digits matches the digits of a valid power of two.
Approach 1: Backtracking Permutations (O(d! * d) time, O(d) space)
This approach generates every permutation of the digits of n using backtracking. For each permutation, skip cases where the first digit is 0 to avoid leading zeros. Convert the permutation to a number and check whether it is a power of two using the bit trick x & (x - 1) == 0. The algorithm explores the full permutation tree, which leads to factorial complexity O(d!) where d is the number of digits. Space usage is O(d) for recursion and the permutation path. This method is straightforward and demonstrates brute‑force reasoning, but it becomes inefficient as digit count grows.
Approach 2: Digit Count Matching with Powers of Two (O(d) time, O(1) space)
The key observation: if two numbers are permutations of each other, their digit frequency counts are identical. Instead of generating permutations of n, compute a digit frequency signature for n. Then iterate through all powers of two within the integer range (from 2^0 to about 2^30 for 32-bit integers). For each power, compute its digit frequency and compare it with the signature of n. If any match occurs, a valid reordering exists. This reduces the problem to counting digits using a simple array or map from the counting pattern.
The iteration over powers of two is constant (around 31 values), so the dominant cost is building digit counts of size d. The total complexity becomes O(d) time with O(1) space since the digit array has fixed size 10. Implementations often use arrays or maps from a hash table perspective to compare signatures efficiently.
This approach avoids permutation generation entirely and converts the problem into a frequency comparison task. Conceptually it blends ideas from math and digit counting to exploit the small set of candidate numbers.
Recommended for interviews: Interviewers expect the digit-count matching approach. It shows you recognized the permutation equivalence trick and avoided factorial enumeration. Explaining the backtracking version first demonstrates baseline reasoning, but the optimized frequency comparison shows stronger algorithmic insight and leads to a clean O(d) solution.
Approach 1: Digit Count Matching with Powers of Two
One approach to solve the problem is to leverage the fact that two numbers with the same digits in different orders will have the same digit frequency (or count of each digit). For the given number n, we aim to check if its digits can be rearranged to form any power of two. To achieve this:
- Precompute all powers of two up to
10^9and store their digit frequency in a set. - For the input number
n, calculate its digit frequency and check if it exists in the set.
The implementation uses an array to count the frequency of each digit in n. It then iterates through all powers of two that can exist within the limits (2^0 to 2^30). For each power, it calculates the digit frequency and compares it to n's. If a match is found, it returns true. If no match is found through all powers, it returns false.
Complexity
Time Complexity: O(1) because the number of power of twos checked (31) and the frequency array size (10) are constant.
Space Complexity: O(1) as only small fixed-size integer arrays are used.
Approach 2: Backtracking Approach
A backtracking method can be employed by generating permutations of the digits of the number n and checking if any results in a power of two. Given the constraint, this method needs optimization to efficiently discard invalid permutations early.
- Generate all valid permutations of
n's digits where the leading digit isn't zero. - Track numbers that form powers of two during permutations.
Permutations in C would require explicit handling of stateful recursion and result collections, a task not directly suited for this predefined response format.
Complexity
Not provided due to complexity constraints in inline format.
Approach 3: 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.
Define a function f(x) that represents the digit composition of number x. We can convert the number x into an array of length 10, or a string sorted by digit size.
First, we calculate the digit composition of the given number n as target = f(n). Then, we enumerate i starting from 1, shifting i left by one bit each time (equivalent to multiplying by 2), until i exceeds 10^9. For each i, we calculate its digit composition and compare it with target. If they are the same, we return true; if the enumeration ends without finding the same digit composition, we return false.
Time complexity O(log^2 M), space complexity O(log M). Where M is the upper limit of the input range {10}^9 for this problem.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Digit Count Matching with Powers of Two | Time Complexity: O(1) because the number of power of twos checked (31) and the frequency array size (10) are constant. |
| Backtracking Approach | Not provided due to complexity constraints in inline format. |
| Enumeration | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking Permutations | O(d! * d) | O(d) | Useful for demonstrating brute-force reasoning or when digit count is very small |
| Digit Count Matching with Powers of Two | O(d) | O(1) | Best general solution; avoids permutations and compares digit frequency with all valid powers of two |
Video Solution
Reordered Power of 2 | 4 APPROACHES | Leetcode 869 | codestorywithMIK • codestorywithMIK • 9,103 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Reordered Power of 2 easy or hard?
Reordered Power of 2 Python/Java solution
How to solve Reordered Power of 2 in O(n)?
What is the best approach for Reordered Power of 2?
Is Reordered Power of 2 asked at Google/Amazon/Meta?
What data structure is used in Reordered Power of 2?
What is the time complexity of Reordered Power of 2?
Ready to solve this problem?
Practice Reordered Power of 2 with our built-in code editor and test cases.
Practice on FleetCode