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 <= 109In #869 Reordered Power of 2, the goal is to determine whether the digits of an integer n can be rearranged to form a power of two. A key observation is that if two numbers contain the same digits, they will have the same digit frequency or the same sorted digit sequence.
A common approach is to enumerate all powers of two within the integer range and compare their digit patterns with that of n. For each candidate power of two, either sort its digits or build a digit frequency count. If the pattern matches the one computed for n, then a valid reordering exists.
Using a counting-based signature (e.g., frequency of digits 0–9) is typically faster than sorting for repeated checks. Since there are only about 30 powers of two within the 32-bit integer range, the enumeration remains efficient. This makes the solution practical with near-constant time complexity and small auxiliary space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Enumerate powers of 2 with sorted digit comparison | O(k log k * log N) | O(k) |
| Digit frequency counting (hash/count signature) | O(k * log N) | O(1) |
Algorithms Made Easy
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:
10^9 and store their digit frequency in a set.n, calculate its digit frequency and check if it exists in the set.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.
1#include <stdbool.h>
2#include <stdio.h>
3#include <string.h>
4
5bool reorderedPowerOf2(int n) {
6
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.
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.
n's digits where the leading digit isn't zero.Not provided due to complexity constraints in inline format.
1Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, problems like Reordered Power of 2 are common in technical interviews because they test pattern recognition, counting techniques, and efficient comparison strategies. It also evaluates how well candidates avoid brute-force permutation generation.
Instead of trying all permutations of the digits, which is expensive, we generate all possible powers of two within the integer limit. Since there are only about 30 such values for 32-bit integers, checking each one is efficient and practical.
The optimal approach is to compare the digit frequency of the given number with the digit frequency of every power of two within the valid range. If any power of two shares the same digit signature, the digits can be reordered to form it. This avoids generating permutations and keeps the solution efficient.
A digit frequency array or hash-based signature works best. It records how many times each digit from 0 to 9 appears in the number. This structure allows quick comparison between the input number and candidate powers of two.
Permutations in C would require explicit handling of stateful recursion and result collections, a task not directly suited for this predefined response format.